We learned that it must be cooked on wood, preferably from a fruit tree (was it the te'enah...). With 1.2 million korbanot, that's whole stands of trees. I thought that you can't be ma'bed (w/aleph) b'yadayim aztzei pri in eretz yisrael?
The Mishnah says that the spit was made from a pomegranate tree ("Rimon"). Regarding the large quantity of spits that must have been used, a spit was made from a branch, and not necessarily a whole tree. Furthermore, it is likely that Rimon tree orchards were planted for the exclusive purpose of providing Rimon tree wood spits to the Jews during Pesach (much the same way date-palm orchards are planted now exclusively for the purpose of providing Lulavs during Pesach). Also, they were not necessarily grown in Eretz Yisrael; they may have been imported.
Regarding your question concerning Bal Tashchis, not cutting down fruit trees, (see Bava Kama 91b), it could be that only branches were used, while the tree itself was left standing and alive.
Be well and l'Hitra'ot