How trivial is it? Would an attacker wanting to do one million attempts easily be able to send each from a different ip?

Most of the time when I see large scale password cracking attempts against customer servers, I have to block large blocks because they're coming from large number of IPs. I had to block most of South Korea at one point, because we saw abusive traffic from millions of IPs belonging to a couple of major ISPs in South Korea (thankfully non of our customers had much if any legitimate traffic from outside Europe at the time).

So the answer is: Some are already doing that.

Bad guys can easily rent time on botnets with hundreds of thousands of ips.

So the solution for you seems to be allowing bad guys DoS your system because bad guys can do bad things, is it?

Is per-IP rate limiting the only one way to respond to auth DoS? Different situations involve different trade-offs.

Rate limiting. Not denying service. Bad guys could cause you to have to wait some number of seconds to log in.