Where did the phrase "Gotta catch 'em all" come from? The slogan for Pokémon was "gotta catch 'em all". But I have never heard that when I was watching Pokémon in the Japanese original with Chinese sub. The Japanese phrase was something along the lines of "Pokémon, caught!" (ポケモンゲットだぜー). Another phrase was also "my goal, Pokémon master!" (めざせポケモンマスター ).  

Where did the English phrase come from?
Where  does this phrase comes from?

According to Bulbapedia, this phrase is a rough translation from the Japanese games :


  The Japanese equivalent is Get Pokémon! (Japanese: ポケモンゲットだぜー！ Pokémon get da ze~!, also spelt ポケモンＧＥＴだぜー！) 




When did the phrase Gotta catch 'em all first appeared?

While the previous answers are correct, it is important to notice that this phrase first appeared on both anime and game.

You can see on the North America's and European's version of the Gameboy game Pokemon Red and Pokemon Blue the same phrase :






But which one of the anime or the game came first?

As @DavePhD mentionned in the comments, Gotta catch 'em all is a registered trademark. One of its first registration on June 23, 1998 mentions 


  entertainment services, namely, arranging and conducting competitions in the field of playing video games; stage presentations; video game presentations relating to video games; production, presentation, distribution, and syndication of animation, motion picture films, and television programs; and production and presentation of video tapes


which includes both the anime and the game. So we can say that Gotta catch 'em all appeared with the general airing of Pokemon in the United States.

Note that the first episode was broadcasted before the game was released in the United States : the TV Show was aired on September 8, 1998 while the game was first sold on September 28, 19981.



1 Wikipedia links : the first episode and the games