This isn't anything new and it has been covered elsewhere in much more detail. However, there are a few ways to speed up Mail. I've tried two. One I highly recommend, the other is up to you because I don't want to be responsible for any problems that may arise as a result of you mucking about with parts of Mail.app that even I don't fully understand.
First, move older email messages out of your Inbox and into an Archive folder. You should have no trouble doing this. It may take a little while for Mail.app to move all of the messages. If you're the type of person that has several folders (or Mailboxes) for message categories like family, friends, work, etc. etc. then you may not benefit from this tip. But, if you're like me, and you leave every single message in your Inbox then you definitely will.
What I've done is move every message in my Inbox dated prior to December 1, 2011 into an Archive folder that is locally here on my Mac. This way when I go into my Inbox it is only loading a few months of email. I may do this again in June or wait an entire year if I don't see much of a slow down. But just doing this has sped up Mail.app a lot.
Second, you could strip the bloat from Mail.app's Envelope Index. What does this mean? I don't really know but the layman's explanation might be this; Mail.app keeps a database and sometimes it gets a little out of control. You can run a few commands via Terminal and it will clean up that mess. Again, do this at your own risk.
Your mileage may vary but with these two tips Mail.app should get just a bit snappier. It has for me.