The folder list dialogs (when moving, or when doing "show other..." folders) has a search icon.
I believe that with a large folder hierarchy, it's just as fast to tap search and then a few characters -- then to expand level 1, find next folder, expand that, find next one, expand that one, finally find the folder you need...
---
But then I don't use anywhere near the number of folders in any of my accounts that some people do...
Maybe something's wrong with me, I should create at least a thousand!