Fundamental to the misunderstanding on resolution is that sensors are usually (physically) 4:3 in aspect ratio - heck, they'd be square if they could, for maximum image information within the circular array of light streaming in through the phone camera lens, but who likes the look of square photos? (OK, Instagram, but that's only at terribly low downsampled quality/resolution)
However, think about printed photos in albums from years gone by. Take one look at TV screens around you in 2013, take one look at phone screens - they're nearly all 16:9 in aspect ratio, i.e. 'widescreen'. Which means that it makes a lot of sense to make the photos (and videos) you may want to display on these screens (etc) are also in this aspect ratio.
In fact, internally, traditional camera phones do capture at 4:3, using the full rectangular area of the sensor, and there's usually an option ("4:3") to switch to this in the camera application's settings. The diagram below shows, diagrammatically, what happens in a traditional camera phone - the whole sensor receives light, but the software (by default) chooses to only grab the cropped area shown, instantly creating a 'pleasing' 16:9 version of the scene:
In most cases, this cropped version works out to around 75% the physical area/resolution of the full rectangular sensor, so typically 6MP output for a '8MP'-rated smartphone camera.
In short, you're not being misled by the phone companies and their specifications, your device really can take 8MP or 13MP (or whatever) photos - you're simply being, by default, led to use a widescreen aspect ratio. No pixels or quality have been lost in your main subject, despite the lower megapixel count, honest! The 'lost' pixels are all on the top and bottom edges and you can change the shooting mode to include these if you really want to.
____________
Things get more complicated (in a good way) when dealing with Nokia's top end camera-toting smartphones, of course. Aside from the well known 41MP high resolution sensors and oversampling, one of Nokia's best (and least known) innovations was to look at the diagram above and realise that, assuming most people want to shoot in 16:9 most of the time and given a specific size of camera and thus optical circle, some pixels were indeed being wasted, at the left and right edges, where a slightly larger sensor could capture some remaining sections of the optical circle, as shown below (applying to most of Nokia's recent top end 8MP devices):
As you can see, the resolutions on offer are now slightly different, since the 16:9 photo being taken is no longer just a crop of the larger 4:3 photo - it's a totally different sampling of the sensor. As shown in the small accompanying text, for this configuration (only used by Nokia, as far as we know), the quoted 8MP resolution only reduces to 7.1MP for 16:9 photos, i.e. more of the sensor's pixels are being used.
Note also that the sensor itself is slightly larger in resolution and is in fact 8.7MP - but you can't take photos at that resolution, since it would involve the corners of the sensor being outside the optical circle (i.e. where light is falling) - so the corners would be dark!*
* Not that this has stopped programmers trying to force the camera to capture in this 'full sensor' mode anyway.
_________________
The big takeaway from all this is that you shouldn't get too hung up on the exact output resolution from your smartphone camera. Detail at the centre of your photo (where you're more likely to be interested in quality), at pixel level, is physical and immutable, no matter how many extra pixels are also captured and rendered around it.
And if you really are passionate about perfect framing and dancing around the differences between 16:9 and 4:3 then maybe you should be standing a little further away from your subject and cropping perfectly afterwards (e.g. here in my infamous panorama 'cheat'!)