rm -r funciona em cada um dos seus argumentos. Se um argumento for um diretório, ele listará o diretório (com o opendir e readdir funciona ou algum método equivalente), e opera em cada entrada por vez. Se uma entrada é um diretório, ela explora essa entrada recursivamente.
Este é exatamente o mesmo método que outros aplicativos usam para percorrer diretórios recursivamente - find , ls -Rf , etc.
A ordem do percurso é imprevisível. Na maioria dos sistemas de arquivos, a ordem é reproduzível desde que nenhum arquivo seja adicionado, removido ou renomeado no diretório (a ordem poderia, em teoria, ser completamente aleatória e mudar a cada vez, mas não consigo pensar em um sistema de arquivos onde isso acontece). Em alguns sistemas de arquivos, a ordem pode, em geral, ser deduzida dos nomes dos arquivos ou da ordem em que os arquivos foram criados ou de uma combinação de ambos, mas você precisa conhecer os detalhes do sistema de arquivos, e isso pode variar dependendo a versão do driver. A ordem de travessia não é algo em que você possa confiar.
Observe que ls ou echo * classificam os arquivos na ordem lexicográfica de seus nomes. find e ls -f não ordenam.
A única coisa em que você pode confiar é que os argumentos são tratados em ordem. Então, se C/ ainda estivesse parcialmente lá, isso significaria que Dest/ estava intocado. Se C/ desaparecer, você poderá ter uma ideia de onde os arquivos foram removidos em Dest/ verificando os horários de modificação do diretório e comparando-os com o tempo em que C/ foi excluído ou a hora em que a cópia foi finalizada. O primeiro arquivo a ser excluído pode ser um arquivo diretamente em Dest/ ou em algum lugar no fundo da hierarquia, dependendo de a primeira entrada em Dest/ que rm ter atravessado ser um diretório ou não.
A velocidade de rm é principalmente uma questão de quantos arquivos há para excluir. É preciso um arquivo muito grande para ter um impacto perceptível no tempo de exclusão. A maior parte do trabalho está excluindo cada entrada de diretório. Os dados do arquivo não são apagados, apagar o conteúdo de um arquivo requer apenas marcar os blocos que ele estava usando como gratuitos, o que é relativamente rápido.