I'm guessing it's because rsync collects a list of files first and then deletes them rather than interleaving the two operations. This would mean latency not getting in the way as much as the read head switches between the filesystem index and the inodes themselves.
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.
That is very odd. Hard to answer w/o looking at the code or using strace. On some filesystems, the directory entry is a linked list of names with pointers to inodes. Maybe rsync optimizes in such a way as to require traversing the list the least amount of times? I'm just thinking out loud here...
