I have read all the current responses, and still do not see an answer, but I too have a desire to remove ALL E mails in the category of "all mail". How do I do this???
Click "All Mail." Select all the messages by clicking the checkbox box, and selecting "All." A sentence will appear at the top of the screen with a link, "Select all X conversations in All Mail." Click that link, which will select ALL of the mail in your Gmail account (not just the first 100). Click the trashcan to delete.