Where are passwords stored for Apple Mail?

Often the easiest way to fix a problem like that is to completely delete the Mail account(s) in System Preferences > Internet Accounts, and add them again. Those steps are described in greater detail here: Set up Mail with email accounts - Apple Support.

It should not be this hard to find and update a password.

I completely agree, but unfortunately the way things are going under the ever-expanding "for your security" umbrella is that user names and passwords simply aren't good enough any more. That's the likely reason you're encountering the password challenge despite the fact you know perfectly well what your passwords are.

It probably has nothing to do with the password at all, meaning that even if you find it in Keychain it won't help. The email service provider is probably more comfortable using a secure webpage with its SSL certificate than a client like Mail which might not be using the (possibly updated) settings and protocols it requires.

That's also the reason for suggesting removing the problematic account(s) and adding them again. If you do that Mail will automatically determine and configure those settings.

At least that's how it's supposed to work. It may be the only way to fix whatever's wrong.

For iCloud mail addresses, your Apple ID is used. For all other accounts, passwords are used in System Preferences > Internet Accounts. On each account, click Details... to edit your password. If you forgot your password, it may be stored in iCloud Keychain. You can access iCloud Keychain in Safari by going to Preferences from the menu bar or by pressing Command-,

It's not Keychain Access.

They are stored in Keychain but depending on the particular Mail account it might be "hashed" and unreadable within Keychain Access. If that's the case it will be "hashed" everywhere else too.

Describe how you're going about trying to retrieve it. I'd be reluctant to post the particular email service you happen to be using on this publicly viewable website but that's up to you.

Better yet, please describe your reason for needing that password. I know you wrote that you need to update it, but that solicitation may be less than accurate, or even worse—a phishing attempt.