Mass Deleting Products performance is ... incredibly slow (hard deletes here; since Deactivated still gets hit by code in other areas, causing slower performance elsewhere). Sometimes, you just have to clean up your data. Please help us help you by cleaning up the databases

OPTI SANDBOX
Progress: 3,200 of 514,643 settled this session (3,200 deleted), 94/min, ETA 90h 45m.
OUR QA ENVIRONMENT (which is way slower than your sandbox, with the indexes)
Progress: 461,200 of 463,366 settled this session (461,199 deleted), 11,646/min, ETA 0m 11s.

All you gotta do is add 4 indexes:

CREATE NONCLUSTERED INDEX IXCustomProductReplacementProductId ON dbo.Product (ReplacementProductId);
CREATE NONCLUSTERED INDEX IXCustomProductDefaultChildProductId ON dbo.Product (DefaultChildProductId);
CREATE NONCLUSTERED INDEX IXCustomOrderLineProductId ON dbo.OrderLine (ProductId);
CREATE NONCLUSTERED INDEX IXCustomOrderLinePromotionResultId ON dbo.OrderLine (PromotionResultId);

And performance for the delete improves by 29,900%