From Forever For Now:
Mail stores a so-called Envelope Index which contains cross references between message subjects, contents and other interesting aspects. Over time, this index becomes less and less efficient and slows down Mail.
The following action performed in the Terminal will clean up Mail's internal database, saving disk space and speeding up the application.
* Quit Mail from the menu or using Apple + Q and wait until the black arrow disappears from Mail's Dock icon.
* Open up Terminal using Spotlight via Alt + Space or start it from the Applications/Utilities folder.
* Type or copy the following line into the Terminal window:
sqlite3 ~/Library/Mail/Envelope\ Index vacuum