I occasionally experience similar slowness. In my case, it's caused by bloated sqlite database. After I delete all history, the browser is snappy again.
It is frustrating that Firefox makes it so easy to delete recent history, but difficult to remove old stuff. I really only want the last month or so; why do I have to clear it manually?
I would, but just recently purged all my history, so I don't have a reference about database size and number of entries. That means I can't include any constructive data in the bug report.
