Since the primary key on the table from which you are deleting records is a foreign key on other tables, check to ensure that the foreign keys are properly indexed on the child tables. If they are not, then the database engine is probably doing a full table scan on the child table for every record you delete from the parent table.

If this is your problem, then it is easy to fix. Just add indexes on the foreign key columns. 🙂

Hope this helps.