The same way that we can make an HDTV the same size as an old low res TV or even smaller. We make the pixels on the sensor smaller.
The sensor size (APS-C, full frame, etc) refers to the size of the area that the light is focused on to. It can be very large in the case of research telescope sensors and digital medium format cameras or very small in the case of things like smartphone cameras and other embedded cameras, or anywhere in between. While it is more difficult to make a high resolution sensor the smaller it is, there is no direct correlation between sensor size and sensor resolution.
Sensor resolution (megapixels) on the other hand is simply the number of points of light that are sampled within the sensor area. The smaller you make those pixels, the more of them you can fit in a given area and the higher the resolution can be for that sensor.
Since we have 13+ megapixel cellphone cameras, that might bring up the question of why do we only have 20 or 30ish megapixels full frame DSLRs (since the sensor is so much bigger). The reason is two fold. Part of it is that while we may be able to make very very small pixels, scaling it up from a very small area presents challenges such as heat management and supporting the structure of the sensor itself. Another part of it is quality of the sensor. We may be able to cram a 13 megapixel sensor into an area the size of a pencil eraser, but the quality of that sensor is nowhere near as good as the quality of a full frame sensor since it can use much more complex sensing. This is also part of the concept behind the so called "ultrapixels" that HTC uses in their lower resolution but in some cases better performing smartphone cameras. Getting functionality like better noise management and faster reading allows for better overall performance of the sensor.
So what is the limit of resolution, well, ultimately, the main issue we run into is something called diffraction limiting. We can make pixels so small that it virtually doesn't make a difference because beyond a certain size, light diffracts and we can't reliably resolve pixels any smaller than that. This is another part of the reason we don't see cameras greatly exceeding the limits of modern high end DSLRs. The advantage of each additional megapixel becomes less and less of an advantage when compared to other areas of gain.