I’m French and while I haven’t yet read The Count of Monte Cristo I read mostly 19th century authors and it is common for characters in books of that time to address each other as “madame” and “monsieur” so it is likely in the original text and wasn’t added in translation simply to convey the formality of “vous”.

French literature can be so formal, not all of it but a lot, I have read novels written in the first half of the 20th century where couples who live together use the formal “vous” to each other.