Clearing your history can definitely take some time, the same occurs on chrome. Nothing can disappear in just a second.

If by "history" you mean only the actual history list, then it should be pretty fast. If you are also referring to the "temporary files / cache" part of the history, then that could amount to hundreds or thousands of files that have to be deleted.

It this with using "History > Clear Recent history" or are you clearing history in the History Manager?

You can check for problems with the places.sqlite database file in the Firefox profile folder.

• http://kb.mozillazine.org/Bookmarks_history_and_toolbar_buttons_not_working_-_Firefox
• https://support.mozilla.org/kb/Bookmarks+not+saved#w_fix-the-bookmarks-file

• Places Maintenance: https://addons.mozilla.org/firefox/addon/places-maintenance/