Photoshop does a really good job of resampling, If your image starts out sharp you can easily double the size with out loosing much detail or at least be able to see it with the naked eye at a reasonable viewing distance.
Or better than double it, depending on whether the original image captured sufficient detail for your purposes.
For the portrait work I do, an important pictoral factor is that viewers have a distinct expectation of sharpness: A portrait is considered "sharp" if the facial hair is sharp when the face is seen at a size at which they'd expect to resolve facial hair with the naked eye.
In practice, if the head size is about 3 inches or larger on the final display (an apparent "distance" at which the naked eye would resolve a person's hair), the hair must be resolved for the image to be considered "sharp." (I always assume viewing distance to be "reading distance" because I find that when viewers are engaged by a photograph--my intent, of course--they will move as close as physically possible to see the detail they expect in a photograph. They don't care about theoretical viewing distance rules!) If the head size is less than 3 inches in the enlargement, viewers don't mind blurred hair because the naked eye doesn't resolve hair when a person is seen from such an apparent distance.
But viewers of portraits don't care to see skin flakes or hair mites, no matter how great the enlargement or how close they get--if the hair is sharp, that is sufficient. The fortunate thing for digital photographers is that hair is easy to interpolate in software--it's just a tone without internal detail. As long as the facial hair is resolved in the original capture, the image can be successfully upsampled to nearly any size.
So the deciding factor becomes the scale of the face in the image, and the photographer has to work within those limits. Any DSLR can resolve facial hair in a head-and-shoulder portrait, thus even the 4- to 6-megapixel older DSLRs did well enough for those kinds of portraits. An 8- to 10-pixel DSLR can resolve hair up to around a half-length portrait, and a 12-megapixel DSLR can get to 3/4-length. At 21-megapixels, hair is resolved in a full-length portrait. This is presuming the head size is enlarged in the final display to 3-inches or greater.
Is it possible to create a successful portrait even if the hair is not resolved in the original image? Yes, but the photographer has to work around that limitation--printing on canvas, for instance, or using Corel paint or a soft-focus treatment to make the lack of detail "intentional."
A landscape, OTOH, is a totally different situation. Viewers expect a landscape image to reveal more and more detail the greater its enlarged and the closer they get to it. Viewers become frustrated at the point they see that there is no more detail to be revealed.
Thus, the resolution requirement for a landscape camera is practically infinite. The photographer has to work within the limits of the equpment by limiting the size of the final display (little or no upsampling) or using as high a resolution camera as is available.