Before you spend any effort trying to get them to change, consider they might be under a requirement you are unaware of. For example, if they are using these passwords to access a credit card environment, PCI DSS requires a periodic password change. This could be something completely out of their control.
If that's not the case, you can try referring them to the latest recommendations of NIST in SP 800-63B. In section 220.127.116.11 Memorized Secret Verifiers (aka passwords), they say this [emphasis mine]:
Verifiers SHOULD NOT require memorized secrets to be changed
arbitrarily (e.g., periodically). However, verifiers SHALL force a
change if there is evidence of compromise of the authenticator.
The entire section on passwords is intended to be read and implemented as a whole, of course, but this recommendation stands on its own. The only complaint I have on the paper is that their recommended minimum length is only 8 characters, which is clearly not enough to withstand a brute force offline attack on password hashes that might be exposed in a data breach. To mitigate that, they do require stored password hashes be sufficiently protected against brute force attacks, such as 10,000 rounds of PBKDF2.
10,000 rounds of PBKDF2 is suggested for online password verification because the idea is to make it computationally expensive to verify a single password, while still allowing for real-time processing during the frequent occurrences of user logins. But note that old password confirmations would happen only during an actual password change activity, which should happen far less frequently than regular logins. And this opens an opportunity to improve your security.
Consider expending extra processing power during the process of password changing. Compute both the PBKDF2(password,10000) and store it in your "everyday password" table, and keep an archive of PBKDF2(password,50000) in your "prior password" table. When they log in again, compare them only against the "everyday password" table. When they change passwords, perform the lookup against all the entries in the prior password table; this will be much slower than a regular login, but because it's infrequent, it shouldn't disrupt your normal business. Once it's verified as unique, discard and replace the existing everyday hash with the new everyday hash, and add the new strong hash to the "prior password" table, rolling off their oldest prior password.
If it ends up that you can't talk them out of periodic password changes, try to get them to at least implement the strongest practical storage of "prior passwords".