From what I've found out, the first first name that could be attributed to Mrs. Claus is Jessica.
Although Santa Claus has been around for generations, Mrs. Claus is a relatively new creation. When first introduced, she didn't have a first name. But the closest first name attributable to her is Jessica. That's because a young Kris Kringle meets and falls in love with her in the classic children's special "Santa Claus Is Coming To Town", which debuted on US television in 1970. He marries her, and she becomes Mrs. Claus.
The second first name would be Carol--as in Carol Calvin (nee Newman), who marries Scott Calvin (Tim Allen) to fulfill the "Santa Clause" in the second and third movies of that series.