Need Help Choosing 110V Relays for Mega 2560

Yes, that would work. It needs a 12V supply for the relays. However, if you look on eBay, you will find lots of inexpensive relay boards, most of which only need 5V.

That's intended to switch low voltage DC, not high voltage AC.