The history deletion of Firefox is very slow and it has nothing to do with the add-on. Try doing it manually and directly in Firefox by deleting 1000 entries and see Firefox hang.

I wrote the add-on to prevent the history from getting large and improve privacy.

Please don't mark the add-on down for a feature request or support queries.
Please post all support questions/requests to the support topic.

The support site is listed on add-on's page under "Support Site". It is also listed on add-on's Help Page.