If the backup disks is full, I'm not surprised doing a backup takes ages. It's got to go through purging stuff on the fly alongside backing up new stuff and constantly rebuilding indexes, which will grow and trigger even more purging requiring more re-indexing. Horrible. Your backup disk should always have some free working space for it to run efficiently.

Can't you reducing the retention period so you always have some working space free, or just get an appropriately sized backup disk? Time Machine backups should run in just a few minutes automatically every hour on a well configured system.