If you have Mudbox, definitely use that instead of doing it in Maya.

This video seems pretty comprehensive for new users. If you’re only interesting in painting textures, he starts talking about that at 27:30

https://www.youtube.com/watch?v=H3qZwt5l3xE

Not quite sure what you mean when you asked this question though:

“Would I be better off painting the model based on reference images of the creature or would I be better off trying to texture the creature using textures?”