After some more investigation, this appears to be a https://www.mediawiki.org/wiki/Page_title_size_limitations condition only, with the interwiki prefix putting the link just over the limit - so now the condition is: the page title is not over the limit itself, but it is failing when linked via wikidata interwiki's - causing a failure for pages that are close to the maximum byte size

The interwiki prefix itself is not counted in the length limit but it causes a namespace to be counted.
I made some tests here: https://en.wikipedia.org/wiki/User:PrimeHunter/Page_name_size_in_interwiki_links

Summary: Page names can be at most 255 bytes excluding the namespace. But namespaces are not subtracted from the length in interwiki links so an interwiki link can currently (22 July 2020) be at most 255 bytes including the namespace. This means some valid pages outside mainspace cannot be linked in interwiki links.

This is also in T29275.