Firstly delete is a very expensive operation in EXT4 due to clearing of the file contents bitmaps among other thing.

rsync definitely builds a list of files to delete first. so that will help.

perhaps it also puts the files in to inode number order which would also help since its related to directory hash order and order of inodes in the inode table.