Rothman can be found in Broken Valley, in a dead-end canyon near the Southern Valley shrine.
He is easy to miss as he is not on the surface and so you cannot see him from a distance. Rothman is in a hole, or to be precise a Troll-hole, and can't get out. Approaching the hole will trigger a cut-scene and give you the side-quest Stuck in a Hole which, simply, is to rescue Rothman. To do this you will need some rope.