I'm guess but it probably depends on who's being choked here. If it's the caller, then it may be the overhead of individual deletions for each record when using the record APIs. If other users are being choked, it may refer to locking.

Naively, I would expect SQLite to be able to delete tens-of-thousands (or even hundreds) of records per seconds, since it's simply appending deletions to the WAL.