When naming Pokemon, always take into account the trainer's character, like age, gender and personality.
For example, a 10 year old who just started out on his journey is far more likely to give their Pokemon a short, straightforward name, while perhaps a more mature, older trainer would give theirs a more sophisticated name. As for gender, a girl is more likely to give their Pokemon a cute/glamorous name, while boys will probably give them straightforward names that sound strong and tough. Also, it's probably likely that girls will name their Pokemon based on how it looks, such as Bubbles for a Marill, while boys will probably take into account it's type, and name a Marill Hydro, or something like that. With personality, it's pretty obvious but I doubt an evil mastermind would name their Marill Bluey, and that's if they had one. Things like social status comes into this as well; a girl from a rich upper class family will probably give her Pokemon a long glamorous sounding name, while a girl from a lower class working family will go with shorter, simpler names.
As for coming up with the actual names themselves, I usually like to take a characteristic of that Pokemon whether it be physical appearance or type and look up the word in other languages such as French, Spanish or German, and then taking that word and arranging it into a name. You could even take two words and arrange it into a name if you wished. And like Mix said, Wikipedia helps too.