I made the mesh first and then painted onto it for the first 3 pictures. On the fourth picture I used an existing map I had, loaded it into silo as a ref image and made the mesh on top of that. I only used PS to effectively add the refpic as a UV texture to the mesh, so no painting as such required.

I'm using displacement painting to make the mesh and loading up a heightmap of a bryce mountain as my pen (set to push). I start with a grid of 100 by 100 faces and subdivide as necessarry, although that has the effect of smoothing and it's a bit of a bind working out which edges to crease. Using the displacement painting tool, you have very precise control about where you want to put mountains, how high you want them etc. I'm thinking you could even make a very high res model with erosion and textures etc, grab a normal map from it and then put that on top of a lower res model.