Apologies for the long break.....
The gemara says that both according to R. Yehuda and R. Shimon it is essential to salt korbanos, but discusses the opinion of the tana of our mishna. Rav Yosef says that according to the mishna 18a the salting of korbanos is the proper method of sacrificing a korban, but the korban is kasher even without it. Abaye argues and says that the mishna only allows the salting to be done by a zar (non-kohen), but must be done. To that R. Yosef responds וכי תעלה על דעתך שזר קרב לגבי מזבח. The implication of Rav Yosef's statement is that a zar can never do melicha because the melicha must be done on the top of the mizbeiach and a zar cannot approach the mizbeiach to salt the korban.
The simple understanding of the gemara is that the only place that the salting can be done is at the top of the mizbeiach. If melicha could be done before the korban is brought up on the mizbeiach it would certainly be possible for a zar to do the melicha and the tana of our mishna could be saying that if done by a zar it is kasher. This would undermine Rav Yosef's entire response to Abaye! The conclusion we must draw from Rav Yosef's response is that the only place that melicha is kasher is on top of the mizbeiach.
The Minchas Chinuch (119) says that although the Rambam writes that melicha is done at the top of the mizbeiach, if it would be done elsewhere it would be sufficient. There is no particular mitzvah to salt it while it is on the mizbeiach, rather the mitzvah is to salt it right before it is burnt, but if done earlier it is also sufficient. The Minchas Chinuch's approach seems to undermine the entire response of Rav Yosef. If it were possible to do melicha prior to bringing up the korban, it would certainly be possible for a non-kohein to do it, and the tana of the mishna would be saying that it is kasher when done by a zar prior to being brought up?
The Shita Mikubetzes (1) asks a different question, but based on his approach we can explain the minchas chinuch's assumption. Although it is forbidden for a zar to go up on the mizbeiach, the tana of the mishna may still be saying that if a zar would ascend the mizbeiach and do the melicha, it is kasher. Why does Rav Yosef assume that the inability of the zar to ascend would invalidate the melicha if a zar does ascend to salt the korban? The Shita Mikubetzes explains that the real problem with the zar doing the salting is that the salting must be done after the kemitzah, and any avodah that comes after the kemitza MUST be done by a kohein. The phrase of "is it possible that a zar would ascend the mizbeiach" is inaccurately focusing on ascending the mizbeiach, but is rather an expression to say that at this stage it is impossible for a zar to be able to do the melicha. Therefore, Rav Yosef argues that the mishna could not possibly be permitting melicha to be done by a zar since it comes after the kemitzah. According to this approach, we cannot prove that melicha must be done on the top of the mizbeiach because that was just an expression to say that the zar cannot be kasher to do melicha.
In conclusion, Abaye and Rav Yosef argue whether the tanna of our mishna is saying that melicha isn't me'akev, or that it is me'akev but can be done by a zar. However, according to R. Yehuda and R. Shimon it is certainly me'akev. The Rambam (Hil. Issurei Mizbeiach 5:12) paskens that melicha isn't me'akeiv any korban except for the kometz of the mincha where it is me'akeiv. Regarding the issue of melicha being done by a zar, the Minchas Chinuch cites a contradiction between the Rambam (Pesulei Hamukdashin 11:7) where he says that melicha is kasher by a zar, and the Ramabam (Bias Mikdash 9:5) where he says that it would be pasul if done by a zar. The Shita Mikubetzes that we quoted above clearly holds that it is pasul since it is after the kemitzah, but the Ramban (vayikra 2:12) holds that it is kasher.