I got an email from amazon yesterday that a list of email addresses and their passwords was found on the internet and mine was on it.
Lifelock sent me a similar notice at the end of July.
Are you sure that was an email from Amazon? Yes, you sign in using your email address but the password would be the Amazon password, Amazon wouldn’t have your email password.
Please read this as it sounds like what you described and could be a phishing scam although some people claim in the comments that it was legit.
Just to be on the safe side, never click on links embedded in an email even if it looks legit, always go to your bookmarked URL or type it in.
If you did click on any links, run a virus/malware scan then log into Amazon directly and change your password again.