Try to delete 4000 files and see konqueror crawl - independent of the used view. I didn't do a full benchmarking, but from statistical review of gdb interrupts I would blame the nested loops in KDirListerCache::FilesRemoved.
*** This bug has been marked as a duplicate of 43356 ***