https://developer.android.com/studio/build/multidex.html
It's really not that bad, It only gets a little squirrely if you're trying to support super old android versions.
I definitely consider a 3X build time increase (not 30 seconds to 90 seconds, but 1 or 2 min to 5-8) to be a significant problem, bordering on nightmare... especially since we just included a few more libraries that put us past the 65k mark.
Is that what other people have seen?
And I can only do that with release builds if I want useful numbers. I've had us split up apps over build times because of Multidex (for example, most of our AWS centric code lives in a separate app that exposes specific functions via an AIDL interface because the SDK was bringing in too many methods)
That said, you can use proguard to strip your unused methods and it usually fine even for large applications.
Given how bloody good Java IDEs are (By which I mean to say - how good IntelliJ is), the cognitive cost of this interface bloat is very low... Until you start developing for Android.
It is more likely that generated classes, countless getters and setters and a tendency to small methods has a higher impact.
I've also heard that scala apps on Android can sometimes hit the limit, because pulling in the scala stdlib greatly bloats the method count.