Since the latest Beta Update, maybe just a coincidence, but clearing all that history does it way way quicker now.

But I still do a, "Click & Clean," afterwards, because I can CLEAR yet SAVE certain cookies there.