In the UK, I believe we might use "Mr Mayor" for a male mayor, or for a female mayor (or mayoress), "Madam Mayor". However, I don't know if the wife of a mayor gets a title of her own if she is simply married to the mayor. Frequently, she is given the role of "Deputy Mayor(ess)" and can be addressed as such, but I don't know if that's the case where you live.
I think calling them "Mr and Mrs Mayor" makes it sound as if "Mayor" is their surname!
The following link may help with other salutations:
Addressing People of Title - Address and Salutation