Tosafos in many places (pesachim 50b for one) asks how are we to reconcile the concept that one should to mitzvos even not li'shma, with the concept that if one does mitzvos not li'shma it is better that he wouldn't have been created. Tosafos always answers that there are different types of not li'shma, if one is doing it for alterior motives it is positive, but if one has destructive motives it is negative. Based on this, the Maharsha (Horyos 10b) asks what is the proof from balak since clearly his intent was destructive to destroy klal yisroel?
Also, R' Eliyashuv points out that if the entire advantage of shelo li'shma is that it leads to li'shma, then what is the proof from balak since his korbanos never led to li'shma?
The Maharsha explains that since Balak felt threatened, his intentions were regarded as a valid form of shelo lishma, rather than being a destructive type of shelo lishma. This seems to be what Tosafos says earlier in Sotah 22b that balak's intention was for personal benefit, not destruction. To answer the question of R' Eliyashuv, the Maharsha explains that "will lead to li'shma" doesn't mean that the person himself will come to do it li'shma, rather it means that the reward even for "lo li'shma" is that it will lead to a descendant such as Shlomo Hamelech doing the same mitzvah lishma.
Another chiddush that we see from our gemara is that the reward that one receives for doing a mitzvah "she'lo li'shma", is both a positive reward for the action, and a fulfillment of his intent even though it was not positive. This is clear from the fact that Balak was zocheh to the reward of Ruth and Shlomo as a descendant, and he succeeded in causing harm to klal yisroel in the time of Elisha because he merited to have his bad intentions fulfilled (as rashi explains).