You might want to have a look at notmuch (http://notmuchmail.org/). Said abruptly, it's a wrapper on top of Xapian (the search engine) that you feed with your email, after which you can query using mail-related queries:

    $ notmuch search from:linus crap

and, most usefully, tag:

    $ notmuch tag +rant from:linus crap

Tags work exactly how you would expect them to:

    $ notmuch count tag:rant

There are myriads of frontends (even a web-based one [0]) if you want to go further than cli.

You're gonna have to transform everything to maildir or mh though (unless you can somehow iterate over your mails from the formats you have), but I guess that's not too unreasonable to do anyway.

[0] https://bitbucket.org/wuzzeb/notmuch-web