The Merovingian (also known as The Frenchman) is said to be a powerful program.
What kind of program is he?
Why is he considered so powerful?
Is he vital to the Matrix in some way?
None of the films explain exactly what kind of program the Merovingian is, but we are given many clues to explain his function and history.
There's no reason a sun-controlling program should look like a little girl. Or an operating system seem to be a sybaritic French gangster.
The sun-controlling program is Sati and the "sybaritic French gangster" can only be the Merovingian, so according to The Kid the Merovingian is an operating system.
Unfortunately, this quote is not very authoritative since (a) it originates from a blog which has been deleted, and (b) it could simply be the opinion of The Kid since no proof is offered.
Nonetheless, we can take the notion that the Merovingian is an operating system as a hypothesis and test it against what we know. And what we do know strongly suggests that the Merovingian is the Oracle's predecessor from the Matrix betas. Everything we know about the Merovingian supports this theory:
The Merovingian is an old program, in existence from the time of the Matrix betas. To support this consider this quote from the Oracle:
[The Keymaker is] being held prisoner by a very dangerous program, one of the oldest of us. He is called the Merovingian, and he will not let him go willingly.
The Oracle calls him a program and considers him a contemporary of hers ("one of the oldest of us"). We know from the Architect that the Oracle has existed since the Matrix betas since she re-designed the Matrix to the current version which allows human choice (albeit at a subconscious level). Therefore the Merovingian has existed since the time of the Matrix betas.
Additionally, the Merovingian himself tells Neo that
I have survived your predecessors and I will survive you.
This indicates that the Merovingian has existed throughout at least several iterations of The One, and possibly all of them (which again means he has existed since the Matrix betas).
The Merovingian's purpose is to traffic information -- as he put it, it is his "business to know". A program that traffics information between programs is a possible definition of an operating system. Moreover, it could also be said that it is the Oracle's "business to know". The two have the same purpose except that The Oracle is better at it (she also knows the future, at least as determined by choices she can understand).
The Merovingian is an exile. Recall The Oracle's response when Neo asks her why a program would be deleted:
Maybe a better program is created to replace it - happens all the time, and when it does, a program can either choose to hide here, or return to The Source.
Again, the Merovingian and the Oracle have the same purpose except that the Oracle is better at it -- so the Merovingian chose exile when the Oracle replaced him and he was flagged for deletion.
The Merovingian hates The Oracle (he uses the derogatory "fortune teller" to refer to her and arranged to delete her shell). If The Oracle replaced him then it is obvious why he hates her.
The Merovingian does not believe in choice (only in causality). For example, he says that
Choice is an illusion created between those with power and those without.
If the Oracle replaced him because she can see into the future based on choices she understands then it makes sense why the Merovingian would deny the existence of choice -- otherwise he would have to acknowledge that he is obsolete.
The Merovingian tries to bargain for the "eyes of the Oracle" in Club Hel. If the Oracle replaced him then "eyes of the Oracle" are what made him obsolete. He would no longer be an exile if he took the "eyes of the Oracle" from her.
The Merovingian and the Oracle share a connection with Seraph. When we first meet Seraph he explains that he protects "that which matters most" -- which is the Oracle. However, Seraph used to work for the Merovingian -- in Club Hel the Merovingian calls him the "prodigal son" and "Judas". If the Oracle replaced the Merovingian then originally the Merovingian was "that which matters most" and protected him. When the Merovingian was exiled so was Seraph. At some point The Oracle must have designated Seraph as her protector, which meant that Seraph was no longer an exile but had betrayed the Merovingian like a "prodigal son" and "Judas".
In summary, everything we know about the Merovingian makes sense if the Merovingian was replaced by the Oracle. Specifically, he could be called an "operating system".
The Merovingian is so powerful because
Not anymore. If he was the Oracle's predecessor then at one time he was "that which matters most". But now he has been exiled and no longer has a purpose within the system (he has been replaced by the Oracle).
Somewhat speculative, but two theories can be extrapolated from information seen in the films:
Persephone mentions at one point that she and the Merovingian "came" to the Matrix, implying that they existed outside of it initially:
A long time ago, when we first came here, it was so different.
Therefore, it makes sense to assume that his function, whatever it was, may have been similar to that of Rama Kandra, and completely unrelated to the functioning of the Matrix.
If this is the case, he, like Rama Kandra, would have come to the Matrix illegally, making it impossible to know exactly what he was initially designed to do. He may have been anything from an alarm clock to a security system to a factory subroutine, but whatever it was, he either rebelled against it or was scheduled for deletion and fled to the Matrix.
The Matrix is famously symbolic and allegorical, and the symbolism surrounding the Merovingian is about as subtle as a shovel to the head: he's the Devil. His wife is named Persephone, he runs a club called Hel, he dresses in all black and red, he's a figure of temptation and sin, etc.
This symbolism could simply be stylistic, but it could also be a reference to his possible function as a deletion program. Certainly, such a program would have incredible power within the Matrix, especially over his fellow programs (whom the Merovingian seems to deal with more than Humans). It would also be an easy avenue toward illegal activity (allowing programs to go undeleted for a price), and it fits nicely with the kind of criminal activity in which we see him engaged (such as "human" trafficking/smuggling of Sati, notably after she was scheduled for deletion).
This is the answer I personally believe, given his onscreen actions and stylistic portrayal.
There exists a theory that the Merovingian used to be a human anomaly like Neo is (a "One") who survived prior iterations and went rogue, hiding in the Matrix. This is hinted at by Persephone:
Persephone: If you want the Keymaker, follow me. [to man in washroom] Get out! I'm so sick of his bullshit. On and on, pompous prick. A long time ago, when we first came here, it was so different. He was so different. He was like you. I'll give you what you want. But you have to give me something.
Persephone: A kiss.
Trinity: Excuse me?
Persephone: I want you to kiss me as if you were kissing her.
Persephone: You love her. She loves you. It's all over you both. A long time ago, I knew what that felt like. I want to remember it. I want to sample it. That's all, just a sample.
Trinity: Why don't you sample this instead?
Persephone: Such emotion over something so small. It's just a kiss.
Neo: Why should we trust you?
Persephone: If I don't deliver you to the Keymaker, she can kill me.
Neo: All right.
Persephone: But you have to make me believe I am her.
Neo: All right.
Persephone: Terrible. Forget it.
Neo: Wait. Okay.
Persephone: Ahh, yes. That's it. I envy you. But such a thing is not meant to last. Come with me.
I have never given this much credence, but it is a possible explanation for his abilities and it is plausible.
Back in the days of the first Matrix (the idyllic world simulation) the Merovingian was a program that was tasked with regulating the behavior of the humans and to report on their progress. When the first Matrix eventually collapsed, the Merovingian was no longer useful and was slated for deletion. Instead he ran away and hid in the Matrix's programming disguised as a human. As time passed he started helping other rogue programs that wanted to escape deletion, gaining more and more power, until he became the undisputed leader of a strong exile community. Powerful enough that both humans and machines would rather not confront him.