My MacBook Air won’t backup to time capsule after Catalina upgrade.
You are in the company of many many people. Catalina has proven that Apple really no longer considers old Time Capsules a viable backup destination.. since they abandoned the whole airport line 2 years ago.
Message says time capsule doesn’t have any room left, but there is lots of room on time capsule
Catalina will start a whole new backup.. it is radically different to what went before.
it was set up to delete old files so this would never happen.
That has never worked properly. EVER!! Just so you know upgrades always messed things up as Time Machine can no longer determine what is needed and what isn't. In the case of Catalina it needs a new backup.
Back to your key issue.
How do I fix it?
You can wipe the TC.. i.e. use Erase Disk button in disk tab. This will remove all your old backups. This is likely necessary but I would hesitate to do it .. you can use Archive function to store your old backups on a USB drive Mac formatted of equal size to the TC disk. Only erase after the archive.. so you can go back and recover files if you need. After 6months or so you will have sufficient history that the archive disk can be reused.

Once wiped Catalina should be able to do the backup. However many people find that is not the end of the problem.. just the beginning.. it requires continual maintenance to work.
If possible I would stop using the Time Capsule for backups. A USB drive plugged into the Macbook will work far better.
If you really want network backups, then I suggest giving Carbon Copy Cloner a try. It is free to download and use all functions for a month. It is not as tightly integrated into the Mac OS as Time Machine but is a heck of a lot more reliable.