I had a similar problem with a bucket containing more than 800,000 objects, the gsutil -m rm gs: // bucket-name method works, but takes a lot of time since it is essentially still deleting each object one at a time.
After we contacted the Cloud Storage team at Google, they pointed me towards the bucket life cycle rules, although they are not instantaneous, they allow me to delete objects more efficiently.
I wrote a blog post about removing full buckets using this method.
source share