I previously mentioned this great tool called FindBigMail which scours through your GMail inbox and tag all large attachments. While the service is free for personal use, you have to pay to use it for GMail for Domains accounts (aka. Corporate GMail).
But thankfully, it looks like the GMail engineers picked up some ideas and implemented the size search within GMail itself. Try typing "size:10m" or "larger:10m" to find emails larger than 10MB.
Aside from the "before:yyyy-mm-dd" date search filter, you can now also type something like "older_than:1y" to retrieve email more than a year old. By mixing this with the "size" search filter, you can now search for old, large email and delete them to free up space!