This is referring to your quota, or space allocation, on the server. To free up space there you need to delete messages or move them off the server to somewhere else.

You can move messages to the Local Folders account in Thunderbird if you want to keep them, thereby removing them from the server.

All Mail is a special googlemail folder. Their philosophy is to keep everything, and to rely on search (surprise surprise) to find things. So all of your email is stored in All Mail, and it is labelled or tagged. In an email client (and to some extent, gmail's own web interface) messages are presented as if they were in folders, according to their tags. The advantage is that a message with multiple tags can appear in multiple folders, but there needs to be only one instance of each message, contrasting with a true folder-based system, where if a message appears in several folders, it means there are several separate copies of that same message, one in each separate folder where it appears. So gmail's approach is more efficient.

Gmail try to discourage you from deleting things. When you delete a message, it remains in All Mail but with a "deleted" tag. To really remove it you have to specifically move it to gmail's Bin folder.

If you have everything you want to keep in Thunderbird, it may be easiest to go to the gmail website and delete it from Bin there. Or try moving it to [Gmail]|Bin in Thunderbird, and then use Bin|right-click|Empty Deleted to eradicate it.

Please note that in the following article, it shows a "Trash" folder under [Gmail]. Mine is named "Bin", but that might be because I'm using a British English version of Thunderbird.

https://support.mozilla.org/en-US/kb/thunderbird-and-gmail