How does rm -r go about recursively removing? In what order?

rm -r works on each of its arguments in turn. If an argument is a directory, it lists the directory (with the opendir and readdir functions or some equivalent method), and operates on each entry in turn. If an entry is a directory, it explores that entry recursively.

This is exactly the same method that other applications use to traverse directories recursively — find, ls -Rf, etc.

The order of traversal is unpredictable. On most filesystems, the order is reproducible as long as no file is added, removed or renamed in the directory (the order could in theory be completely random and change every time, but I can't think of a filesystem where that happens). On a few filesystems, the order can in general be deduced from the file names or from the order in which the files were created or a combination of both, but you need to know the fine details of the filesystem, and it could vary depending on the driver version. The order of traversal isn't something you can rely on.

Note that ls or echo * do sort files in lexicographic order of their names. find and ls -f do not sort.

The one thing you can rely on is that the arguments are handled in order. So if C/ was still partially there, it would mean that Dest/ was untouched. If C/ is gone, you can get an idea of where files have been removed in Dest/ by checking the directory modification times and comparing them with the time C/ was deleted or the time the copy ended. The first file to be deleted could be a file directly in Dest/ or somewhere deep in the hierarchy depending on whether the first entry in Dest/ that rm happened to traverse was a directory or not.

The speed of rm is mostly a matter of how many files there are to delete. It takes a very large file to have a noticeable impact on the deletion time. The bulk of the work is deleting each directory entry in turn. The file's data isn't erased, erasing a file's content only requires to mark the blocks that it was using as free, which is relatively fast.