Passwords are only verified on login. Does it seems reasonable that there are millions of logins to Gmail from mobile devices every second?

Back of the envelope: 2 million logins per second would mean about 170 billion logins per day. With 7 billion people on the planet, that'd mean about 25 logins per day from each man, woman and child.

“Up to 3x the work” is very misleading, since the average will be much less than 3.

I would imagine it's sequential: check exact match hash, if it fails check uppercase-initial-hash, etc.