If you really have to loop through the entire set deleting record by record, I'm not surprised it's slow. Could you change your application to loop through the records doing "stuff" without deleting (maybe even "do stuff" en masse), and afterwards do a mass delete ?
I also have a nagging suspicion (unfounded by any actual experience, though) that it might be faster to cut the explicit relations and do the child deletes as a separate single-block execute, too. Easy enough to test, I suppose. -- Bier met grenadyn Is als mosterd by den wyn Sy die't drinkt, is eene kwezel Hy die't drinkt, is ras een ezel