Updating large table worked before, now taking hours
It might help a lot if you would have listed the indexes you have or the query plan. If the columns 4, 5 or 6 are indexed, that can slow the process down, and having a clustered index on columns 1, 2 and 3 should speed it up.

If columns 4,5 or 6 are variable length (e.g. varchar) then updating new value can cause a lot of page splits, that definitely will make it slower.

I think what John M meant was that if there's a reasonable amount of distinct values in for example column1, you could first collect the distinct into a temp. table and then run the update separately for each of the values because doing the joining the tables in smaller parts is usually a lot faster.

Of course everything depends on several things, like data types, number of distinct values in the columns 1-3 etc.