The problem is likely a thing called the "tipping point". Every system has one. On my older computer at home, the tipping point comes into play for over 3 million rows (depending on the width of the table). It takes just 3 seconds to update 1 Million rows. For 2 million rows it only takes 6 seconds and for 3 million rows it takes only 9 seconds. All as expected. For 4 million rows, though, it takes well over 2 hours because I've gone past the mysterious (related to the amount of memory available) but ever present "tipping point". You also have to consider what a mega-update does to the log file even if you're in the simple recovery mode.

I recommend breaking up the updates along with a proper index so you can have an expedient WHERE clause to filter out the rows that have already been updated. The index does not need to be permanent.