It might be that they are deleting each entry in its own transaction. A transaction causes file system level sync and with the millisecond latency of common hard drives it causes transactions to have a millisecond overhead. Multiply this by a few thousand and you get the latency you are talking about.

I've made this mistake myself in a project of mine and after tracking down the bad performance to this issue ended up adding a layer that emits explicit transaction begin/end statements after N operations.

Edit: See the bug thread linked in the sibling comment. The transaction latency seems to be a component, but other issues remain.