In my world, there is a race of intelligent, sapient creatures that resemble large cats. They have fur, tails, and whiskers, and can purr and meow like regular cats, but they can also walk upright on two legs and use their front paws as hands. What would be the best way to go about creating a language for these creatures that sounds like a mix of meowing and purring?
You would start with the phoneme-inventory. What kind of distinct sounds can these creatures make? How can they be combined to form longer units? Would there be a gesture-based system? A sound could have different meanings whether the tail is wagging or not, for example. You probably end up having very few distinct sounds, so that's a constraining factor.
Then think what they would talk about most commonly. Food? Interpersonal relationships? Assign shorter units to more frequent elements.
As for grammar, that's really up to you -- there's nothing inherent in the nature of the speakers that influences the grammar.
As inspiration for a language that has a small vocabulary and simple syntax, have a look at toki pona; that might be a good starting point.
You might want to take a look at the Kzinti language (the "Heroes Tongue"), created by Larry Niven for the Kzinti (pretty much the creatures you described), in his Known Space Universe.
While it has a limited lexicon, it does have a complex system of modes and accents, based on feline anatomy, that may help you develop your language.
Given the behaviour of cats, the Kzinti have a society based on dominance and are very warlike. This is reflected in their language, as modes vary based on the rank of the person you are talking to. Modes are implemented by using the wide range of vocalizations cats can make. This range also contributes to complex melodic accents.