I think they are perfect synonyms. I think they are interchangeable. One dictionary simply defines "maybe" as "perhaps," and "perhaps" as "possibly but not certainly: 'maybe.'"
I can think of two situations where we use "maybe," but cannot use "perhaps."
1) "Maybe not" is natural and common. "Perhaps not" is uncommon.
2) We can use "maybe" informally as a noun, to mean a decision that is still uncertain.
Here are some examples.
"That cloud looks dark. Maybe it will rain."
"That cloud looks dark. Perhaps it will rain."
Here are two examples where "maybe" is natural, but "perhaps" would not be used:
"Are you going to go swimming this weekend?" "I haven't decided. Maybe, and maybe not."
"Are you going to buy a new car?" "At the moment, it is still a maybe."