I agree with Marcus A, except I'd use a commit frequency based on time rather than number of records. If you need concurrency with application users, probably 15-30 seconds. If you don't need concurrency, 60-120 seconds. If you want to do the record count, you can experiment with the number of deletes per commit to get to the desired frequency.
Another option is to code the stored proc to delete ranges that are passed as parms. That way you could run several instances of the stored proc concurrently each deleting a mutually exclusive range.