If you're using the stock Mail app, I recommend getting rid of it and getting K-9 Mail. It's a lot better than that stock app, by a long shot. And it does have a Select All feature. Also, I just found out that if you swipe across a message, it will put a check mark next to it, then you can tap on any other message to do the same thing and delete multiple messages at one time.