As mentioned by Count Zero below, the best bet for the quantities involved will be some sort of indexed database for storing the info you want about each mbox path. Something like sqlite should do reasonably well, and will be easy to put in place.

As for traversing the directory tree to get information, you might want to have a look at a script that I posted here a while back: Get useful info about a directory tree. It was designed to do the fastest possible traversal of a directory, and produce a one-line summary for every directory in the tree. You could use it as-is to get summaries for (particular portions or volumes of) your system (the man page is included in the script), or you can adapt the approach used there to your own needs.