there are many causes for performance. but it's good to post little bit more details about this.

Like, do you have created index on some column if yes which type, do you use somewhere have transaction where this tables is used,

i don't know, try this

select T2.COL1, T2.COL2, T1.COL1, T1.COL2, T1.COL3,

CAST(T2.COL1 as VARCHAR)+'-'+CAST(T2.COL2 as VARCHAR)+'-'+CAST(T1.COL1 as VARCHAR)+'-'+CAST(T1.COL2 as VARCHAR) tmpColumn into #temp

from T1 (nolock) join T2 (nolock) on T1.COL4 = T2.COL3

where T2.COL4 != 'data1'

and T1.COL1 is not NULL

and T1.COL5 is not NULL

and T1.COL6 = 'data2'

insert into T3

select * from #temp where tmpColumn not in

(select CAST(COL1 as VARCHAR)+'-'+CAST(COL2 as VARCHAR)+'-'+CAST(COL3 as VARCHAR)+'-'+CAST(COL4 as VARCHAR) from T3)