In terms of development, no, the data layer code grows sublinearly with the with the size/breadth of the schema/data. The data access layer is not much more than a database (plus usually, to enable event-driven programming, some semblance of subscriptions/notifications when data in your query changes). But it's fairly generalizable, and doesn't depend on the size of the team or schema using it.
> Is O(N^2) really that big of a problem? It seems like the problem can be reduced to something simpler: developers cannot easily understand which services communicate with one another. If that is the case, would a visualization tool be sufficient?
It really depends on how complex the system is. At some point, a visualization stops being helpful. There's obviously room to simplify a SOA dependency graph to look reasonable, and many do this successfully. But DOA is another interesting option in the toolkit: turn the problem on its head and say: maybe there's no graph at all.