Descobri que o rsync finalmente faz o truque muito bem, exceto que você tem que remover as pastas que o processo deixa para trás. Infelizmente, mas como as pastas consomem muito pouco espaço, é insignificante e a rm é aceitável:
rsync -axvES --remove-source-files src_folder /dst_folder/
rsync -axvES --remove-source-files /old_dst_folder ./