Thanks to steabert on stackexchange for posting this helpful tip!
In Gmail, simply search for “size:xxxxxxxx“
This undocumented search parameter will help you find messages larger than the size you searched for.
The search parameters are in bytes, so 10485760 = 10MB or 52428800 = 50 MB, and so on.
EDIT: As of November 15th, Google has officially released support for this feature
“To find emails larger than 5MB, you can search for size:5m or larger:5m“