Я бы использовал os.walk для перехода по дереву файлов.
Для каждого файла я бы сохранял имя absolutepath +, проиндексированное по размеру файла и сигнатуре (первые 16 байтов? Хеш первых 512 байтов«Хэш полного файла»).
Когда вы закончите, вы получите набор размеров файлов;для каждого размера - файл подписи файла;для каждой подписи - список всех файлов, разделяющих эту подпись.Если ваша подпись файла не основана на полном файле или имеет значительную вероятность коллизий, вы можете выполнить более глубокое сравнение только этих конфликтующих файлов.