Consider the fundamental difference between the two: Phong shading makes a mesh look smoother, but doesn't change the mesh itself whereas interpolating the surface with additional vertices does.
Thus, Phong shading allows you to get by with fewer polys, but can lead to certain artifacts. In particular, when you look at the profile, you still see the edges & if the poly count is too low, the profile appears blocky.
Interpolating the mesh will smooth out the profile, but increases the poly count. Also, unless coupled with decent shading, the individual facets may still be noticeable on curve. Because of this, the two are often used together to some degree.
As an example, consider the reference image from wikipedia:
You could add more polys to the image on the left, but it's still going to have something of a disco ball sort of a look due to the flat shading & it would take a lot of subdivisions to overcome that problem. The image on the right has a much smoother looking interior, but you can still see the straight edged outline because Phong shading doesn't change the mesh. Softening the outline would take more polys.