As specified in Shulchan Aruch, OC 32:12, t'filin can be made from an animal that died by any means, not just via kosher slaughter, so there would be no need for the Jews to wait for kosher-slaughtered animals after they got the Torah.
(This doesn't preclude their waiting for other reasons, which other answers may yet explore.)
A tip of the hat to Double AADouble AA for this answer. He posted it as a comment on the questiona comment on the question, but it really is an answer. He's not posting it as such for whatever reason, so I'm doing so. But I'm posting it as a "community wiki" answer so I don't get the reputation points from it.