It's pretty close to the service provided by Pwned Passwords [0], but automated.
The key trick to what Google are doing is that Google never ends up knowing anything about what their users passwords are AND their users never end up knowing which passwords Google has discovered YET between them they arrange that the user knows if any of their passwords are known to Google. Magic!
With Pwned Passwords users can learn any arbitrary subset of the Pwned Passwords full password hashes they please for just one API call per prefix - with Password Checkup you have to start by guessing a username plus password combination, then do a bunch of fairly expensive operations, and you only get back a boolean. It's essentially never worth it for bad guys who are guessing.
This has two advantages, and doubtless both are attractive to Google although one advantage is better PR than the other
1. Bad Guys can't sieve the Google system for valuable data. For Pwned Passwords this isn't a big concern because Troy is using readily available password lists. Spending say $5M to get the raw passwords Troy used as input back by processing Troy's data makes no sense, just download a Torrent of it. But Google's Password Checkup doesn't just use public sources. Spending $5M (again just an example figure) to steal data from Google that may not be available to your criminal gang otherwise might be worth it for a big enough score. And it'd be bad PR for Google if a customer gets attacked by such crooks using data which those crooks couldn't have obtained at all without Google. Troy can always say "This data already existed, I didn't make the problem worse" but Google's non-public data can't make that claim.
2. Good guys can't either. Google has a valuable service here, locked into Google's infrastructure. They can choose to give it away, but they could also (as they have with some other products) later decide they'd prefer to monetize it. Either way, nobody else can duplicate it even though millions of people are using it, thanks to cryptography.
The costs are pretty enormous too. Pwned Passwords is mostly just a CDN, and clients are trivial. The upfront maths to make it work was hard, but that's a one-time thing. But Password Check incurs a considerable ongoing cost for Google to do hard maths AND each client needs lots of RAM (this is a memory hard problem on purpose, to exhaust bad guys who might try to exploit it)
Regarding costs, the one-time hash performed on intake is indeed computationally expensive. However, for queries the only cryptographic operation required is a single elliptic curve computation (using secp224r1) on the hashed record sent by the client. Computationally, that should be in the same ballpark as establishing a single TLS connection.
The primary expense (detailed in the paper) is bandwidth, on account of sending out an entire hash bucket with each response. The analysis in the paper assumes a 2 byte prefix, but they're using 3 bytes here to reduce bandwidth at the expense of privacy; for every query made, they have to send back ~250 values instead of just one.
This "But Google's Password Checkup doesn't just use public sources" is infering that Google's db is bigger and better. You don't know and this is example of magic lotion marketing.
"Our magic lotion for hair grow is muuuuch better, as it have secret formula".
Actually I suspect that Troy's db as for now is better/bigger.
Didn't you ever wonder when you see viable SQL injections and other attacks announced so frequently why Troy's data set is so small? Troy is taking the ethical high ground by not buying data. So his data is the tip of the iceberg.