OK.
I don’t think that this is resource intensive. I’ve just deleted one URL with more than 6.000 visits from my history in less than 2 seconds. This is, by far, the worst scenario for me (my second most visited URL has the half of this number of views).
This little hang should be noticeable only in the most frequent URLs, with hundreds or thousands of views. And this should happen only once for each URL, because in the next time there will be only 20 visits at most and only the oldest will be removed, for sure without any delay.
The intention with this feature is exactly to keep history database efficient without having to clear the history (btw, at the moment my places.sqlite size is 120MB).