You can mitigate this almost completely by finding that "database of usernames/passwords sourced from elsewhere" (they're not hard to find) and blacklisting them. Users should not be allowed to use any breached password when they register. A simple message saying "this message was included in a recent password breach and is therefore not secure" should suffice to prevent users getting annoyed that they can't use their favourite password on your site.

Enforcing a minimum length of 10 or even 12 is a great way to eliminate nearly all previously leaked passwords from being used on your site, and it further encourages users to use password managers.

Passwords are shit, but they're here to stay for a while still.