Help optimising delete statement
I've run into this kind of performance issue before, and breaking the delete up into discrete steps of a fixed size is what ended up doing the trick.  It allows SQL Server to commit changes more frequently, which is generally easier on the transaction log.

SELECT 'Begin Delete'; --gives @@ROWCOUNT a value
WHILE @@ROWCOUNT &lt;&gt; 0
    delete top (100000) from [dbo].[tbl1]
    where exists (
        select *
        from [dbo].[tbl2] t 
        where [dbo].[tbl1].[col1] = t.[col1]
        and [dbo].[tbl1].[col2] = t.[col2]
        and [dbo].[tbl1].[col3] = t.[col3]  
    );


The optimal batch size just depends on your server and what it can handle.  I've found 100,000 to be a safe size for me, and we've not got anything particularly powerful, so you may be able to get away with more.