Well it quite much depends. In general its not so much about speed becasue of mel inneficency but rather because its impossible to do algorithmic design with mel so any task that would benefit form a acceleration structure would become fstaer once those complexity slopes are taken care of.
Then theres the systemic flaws of many mel and other programmers who dont recognize the difference between a scripting language and programming language. To be honest theese guys suffer from another problem in even a real programming language but here they loose speed. See if you treat a scripting language call equal to the functionality of the library calls your grossly mistaken, the library call IS as fast, sometimes faster than what could be achieved with the API. But the computation in mel is not.
Sometimes theese manifest themselves as a feeling that theres something ugly going on in mel. This it seems to me is INTENTIONAL, as it gives you a marker for knowing that the part of your code is supposed to be done in other ways, or the API. To say one such example is making a for loop to set multi attributes, slow as hell. Mainly becasue your not emant to do so, often you can leverage the job to a node instead. This is by far the hardest part to get as a programmer. So lets take a example, lets suppose you want to collapse the tweak array of a shape node to 0, what to do? Well you could just go and write each of the tweak arrays values to 0, but thats VERY stupid. When you could do instead is delete the shape make a new one and connect it into the existing network. It would accomplish the same thing, better yet it would accomplish the same thing FASTER then trying to loop them in the api. Tough granted just porting that code to c WOULD be a lot faster, for one the loop in this case would be slightly faster each turn, however unknown to you the api would result in a O(n) algorithm whereas your mel code would be a quite fast O(n^2) algorithm. wich could even in pure mel code be sloped to a slowish O(n) with a lot stupid code.
Would this kind of functionality be better implemented as a plugin?
Well its a bit misleading thinking. Partly because it assumes its a plugin vs script and nothing in between. The smartest and most productive thing is to do something in between. And that is to convert a PART pf your code to pure API code and still do the bulk of the code in script. Its far faster to do for same end result but its also easier to maintain.
Almost all the best plugin tools that arent just nodes contain a LOT of script with the plugins. Mainly because this way you get there earlier but its also better for the end user as they can make the small required customizations themselves. Its not about anything else. Its a nobrainer less work product faster out, and as a side effect better product for end user that may or may not never need to touch this. Its also easier to support, instead of sending key customers new beta/fix versions when they encounter a problem you MAY just send the relevant script entries for them to look at, this makes the turnaround time faster, and you dont need so high level support staff to be involved.