Isso provavelmente se deve a diferenças no tamanho dos diretórios individuais nas duas árvores de diretórios. Cada diretório é representado no disco por alguns blocos de disco que armazenam os nomes dos arquivos no diretório. Esses blocos são às vezes chamados de "arquivo de diretório". Quando você executa "ls -l" ou "ls -s", o campo de tamanho de um diretório é o tamanho desse arquivo de diretório.
Quando você cria um arquivo em um diretório, o nome do arquivo é adicionado ao arquivo do diretório. Se o arquivo de diretório não contiver espaço suficiente, ele poderá ter que ser ampliado adicionando outro bloco de disco. Quando você exclui um arquivo de um diretório, o nome do arquivo é removido do arquivo de diretório, deixando algum espaço não utilizado. O espaço não utilizado pode ser usado para armazenar outro nome de arquivo. Mas não é retornado ao sistema operacional, portanto, o arquivo de diretório pode aumentar de tamanho, mas nunca diminui.
Se você fosse comparar as árvores de diretório lado a lado, provavelmente descobriria que alguns dos diretórios correspondentes tinham tamanhos diferentes. Isso geralmente significa que um diretório costumava ter mais arquivos nele, ou arquivos com nomes maiores, ou tinha muita "suposição" de criação / exclusão de arquivos no passado.
Quando diff compara dois diretórios, ele verifica apenas se os dois diretórios possuem os mesmos nomes. Ele não verifica o espaço não utilizado nos respectivos arquivos de diretório e não se importa se os dois arquivos de diretório são realmente do mesmo tamanho.