I had this same problem. I installed the beta of Catalina back in June, but then decided against that and did a clean install. Then this month, I installed the release version of Catalina. So I also had two Catalina installs and two "Macintosh HD - Data" partitions. Here is how I solved the problem:
- Opened Disk Utility
- Found the partition that was only 1.6MB (the other was 185GB)
- Unmounted this partition
- Deleted this partition
- Rebooted
- Time machine works!
Please note: I am not an expert in APFS and it's entirely possible deleting that partition is going to cause me problems down the road. So if you do this make sure you're comfortable deleting a partition. Cheers!