When I created my gmail account, there was a counter giving you everyday more space. They "sold us" the product as if you never had to delete email again. By looking at that counter it seemed that by now I should have more than a Terabyte of data, truth is that after many years I have less than 8GB. Although it's a lot of space for the email, if you have automatic notifications, reports, and so on... it's easy to see how you are fastly approaching to the limit.
So, from time to time, it is needed to clean up a little bit your GMAIL account. At least for old reports and automatic emails which may not have sense anymore.
I usually delete some of this nonsense emails by typing in the search box:
Instead of "Label_to_delete" write a "secure" label you want to clean. I say secure because if you label your email with vague rules it is possible that you delete something you shouldn't.
When the search results appear, select the checkbox to check them all, and then click on the link that selects all the items matching that search. With this you will be able to delete thousands of undesired emails in a couple of clicks.
The search box of Gmail is very powerful. If you are used to code, you'll find how easy is to add conditions. A very simple example of that would be:
label:CRONS after:2011/01/01 AND before:2011/02/01 AND from:root AND !has:attachment
Translation: Delete emails coming from CRONS in January coming from root user and without any attachment.
Give it a try!