Please ensure that you do not have an add-on or third party program that will prevent Firefox from deleting history.

This can also be the sign of malware or another infection.
Please scan your computer for infection. Here are some great free tools: Sometimes a problem with Firefox may be a result of malware installed on your computer, that you may not be aware of.

You can try these free programs to scan for malware, which work with your existing antivirus software:

• Microsoft Safety Scanner
• MalwareBytes' Anti-Malware
• TDSSKiller - AntiRootkit Utility
• Hitman Pro
• ESET Online Scanner

Further information about issues caused by malware can be found in the Troubleshoot Firefox issues caused by malware article.

I ran a full scan with AVG; no threats found.

Please try starting Firefox safe mode and then deleting your history while in safe mode.

For more information about safe mode, please view this Mozilla help article.

Problems with bookmarks and history not working properly can be caused by a corrupted places.sqlite database file.

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