Unfortunately, newer file systems optimize for lookup at the cost of delete. We worked around the problem by dividing intermediate files up into separate directories, trying to limit a directory to about 3K files.