Efficient manual cleanup of foreign keys in MySQL
Try batching the deletes, so that you are only checking a small set of records at a time, and so are locking a smaller set of records.  You can play around with increase or decreasing the size of @batchSize until you find the "magic number" that performs best for you.  Note: I don't normally work in MySQL so my while loop syntax may not be 100% correct, but the general idea is there.

DECLARE @i int;
DECLARE @batchSize int;
DECLARE @maxKey int;

SET @i = 0;
SET @batchSize = 2000;
SET @maxKey = (select max(id) from t2 where t2.tl_id IS NOT NULL);


WHILE (@i &lt; @maxKey) DO
BEGIN
    DELETE t2
    FROM t2
    LEFT JOIN t1 ON t2.t1_id = t1.id
    WHERE t2.id &gt;= @i and t2.id &lt;= @i + @batchSize
        AND t2.t1_id is not null
        AND t1.ID is null
    ;

    SET @i = @i + @batchSize;
END WHILE