It's actually around double the size of San Andreas' map. SA just seems bigger to you because of 1) nostalgia, 2) they crammed 3 (smaller) cities into the map, and 3) SA had such a terrible draw distance that it was impossible to get a sense of its true scale. This render from a map viewer
gives a good idea of how far away Mt Chiliad really was from the desert region, which was pretty much on the opposite side of the map.
Not to mention that areas in SA were locked until certain story points, which I think contributed to the feeling of it being larger, as the game gave you a roundabout path taking the long way around to Vegas until everything was unlocked. Once everything was unlocked, you could get from one end of the map to the other in about 2 minutes or less depending on the speed of the car and the roads taken. The vehicles you first get also contribute to the feeling as it's only once you get to Vegas that you start seeing some of the faster cars.