It sounds like you’ve already resolved this, but for the benefit of any others that stumble upon this, my solution for deletion of a large bucket is to set a lifetime rule with a short TTL, after which the objects are deleted.

Set that rule, and come back to a beautifully empty bucket 24 hours later, after Amazon’s gnomes have takes care of the issue for you.