Are there halachas for how an animal for tefillin must be killed? Or can it, for example, be shot, assuming it was shot by a non Jew.
If there are no restrictions, why not? (one would think that we have laws to prevent cruelty to animals.)
In Kesses Hasofer (written by the author of the Kitzur Shulchan Aruch (Rabbi Shlomo Ganzfried)) it seems that if the animal was killed without shechita, its skin is of the lowest quality.
See the end of siman 2 sif 1:
וגם עור שליל מקרי עור לענין זה וכותבין עליו ם״ת תו״מ והוא המובחר ואחר כך עור העוף ואח״כ עור החיה ואח״כ עור בהמה ואחר כך עור נבלה
... and also the skin of a fetus is considered skin for this, and we write on it safer torah, tefillin and mesusot, and it is the best quality leather for safrus. And the next best thing is the skin of a kosher bird (that has been slaughtered) and after it the skin of a wild animal (slaughtered) and after it the skin of a domesticated animal (slaughtered), after it the skin of a nivaila (carcass -- animal not killed through kosher slaughter)
There are no such laws specific to Tefillin though you are correct that we have laws prohibiting cruelty to animals in general.