Without seeing the exec plan, I'm guessing...
The spools are likely an optimisation for the deleting of the rows from all the nonclustered indexes. You could try dropping the indexes and rebuilding them after the deletes are complete.
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability