Like jfroebe said - the most likely problem is that you don't have the correct index on the target table - this sounds like a table scan for each row you delete, which seems to match the performance problems you see.

Michael