Certainly one factor that is contributing to the deletion taking so much time - it's still going on, and probably won't complete before tomorrow at this time - is that there are tens of Gigs of data in that folder. How? Why? I don't know, but I would certainly like to. Such a large volume suggests a run-away process, no?
From what I've seen, many - if not most - of the files currently in the Temporary Internet Files sub-folder are .asmx files, which I understand means that they're 'web services'. Who, or what, creates them in such large numbers? Why? What are they, and what are they for?
Checking the IE settings mentioned (directly, in Internet Options, from within IE, because I've deleted the desktop shortcut) shows that only 8 Megs - apparently the minimum - were allocated to keeping the History for IE. This is now at 32. This suggests that the files aren't being put there by IE - assuming that it's respecting its settings.
I suspected that the AV would slow things down considerably, but I'm not the only user, so left it running; I doubt that it would be wise to turn it off if the machine remains connected, and even if I unplugged the machine, the next user might well come along and simply re-plug the cable, which could be disastrous if the AV is inactive.