Now that gcloud storage has been released, the Google Cloud documentation recommends using it instead of gsutil. One can execute:

gcloud storage ls --recursive 'gs://bucket/folder/**' | wc -l