Demora um tempo constante para desvincular um bloco único , mas arquivos além do tamanho de um único bloco consistem em vários blocos vinculados, e quanto maior o arquivo, maior a quantidade de blocos que estão ligados.
Meu entendimento é que executar rm em um arquivo simplesmente o desvincula, marcando o espaço como livre no sistema de arquivos. Deve-se então concluir que a exclusão de um arquivo sempre leva aproximadamente o mesmo tempo (ou seja, a velocidade de exclusão é proporcional ao número de arquivos, não ao tamanho dos arquivos).
Então, por que a exclusão de um arquivo de 15 GB leva mais de um minuto com um simples rm file.tar.gz ?