Mutt, as with other MUAs, creates a header cache so it only needs to
read the headers of new mail files. If you're slowing down with large
maildir folders, the most likely problem is that your header caching is
not working properly.
There a set header_cache option to add in muttrc.
I use mutt+maildir+procmail on ext3 for my work mailbox, can't tell too much about speed because I often purge messages and got ~100.