Michel, a few questions...

For the table in question....are there indexes and/or relation/constraints involved, and/or any delete triggers?

Also, have you looked at the execution plan?

There are different possible optoins....if the table has an ID you can use (for the IDs to be deleted), if you're passing them in the same order as the original table (if you're using a clustered index), you may get more cache hits.