Envelope Index (see “What’s in your Mail folder?”) is an SQLite database that stores key information about your emails. Over time it can get terminally corrupted (see “The dreaded ‘your home directory is full’ message”).
It can also suffer a large number of smaller hiccups and corruptions which slow Mail down, although they don’t knock it out.
A poster on macOSXHints explains 
how his database stored phantom messages from an Exchange server he used over Summer.
Quitting Mail, dragging the Envelope Index to the Desktop, restarting Mail and allowing it to reindex his emails, cut its size from 200MB to 2MB. The speed increase was significant. Rob Griffiths reduced his from 25.9MB to 4.5MB.
My result was less dramatic (21.6MB -> 17.6MB) but Mail.app still feels a little more zippy.
Worth a shot for you too, perhaps? If so, first make sure you have a backup of your ~/Library/Mail folder in case something goes wrong. Dragging it out of Finder onto your Desktop will do the trick.
