Syncthing is also an option.

Have a look at rsync-sidekick maybe.

I found an answer on StackExchange that refers to a tool called rsync-sidekick which looks like it could achieve your aims.

Edit: There is also another answer on that same StackExchange page referring to a script called rsync-prepare which is capable of working with a remote destination.

As long as the backup system performs deduplication, it should be able to store the backup data efficiently even if the source files are constantly moved around or renamed.

ZFS snapshots can perform deduplication. There is also ZBackup, which also has deduplication support.

Why not exclude the folder you want to move from the initial sync, and sync that folder separately to the final location?

lsyncd does just this. It’s intended use is to sync directories between systems over slow(ish) uplink, but it can work locally as well. It takes some fiddling to set up, but once set up it just does it’s thing seamlessly at the background. However if you’re just looking for a backup solution I’d might look for something else, like a plain rsync script.