One of the 60 sub-folders of my IMAP inbox currently has over 9,400 messages. I've not noticed any problems so far. Due to server-side filtering I've never had more than about 50 messages in the root folder itself which, as you suggest, may be significant.
FWIW, I used MohammadAG's patched Modest on PR1.2. On PR1.3 the default Modest install is fast and reliable enough for my needs.