First, the matrix in question is the "view matrix," which yields the scene coordinates relative to the camera. The "projection matrix" is responsible for the actual warping of the objects as a function of distance to give the perspective projection from which we see the world with our eyes/cameras.
In my mind, the "move the world, not the camera" is a false dichotomy. Ultimately, the job of the graphics pipeline is to get arbitrary scene coordinates mapped onto pixel coordinates.
Consider an orthographic projection that maps the screen to a region that is 100 meters wide (say, for a top-down 2D game). If this camera is at x = 0m, an object at x = -50m will be at the left edge of the screen, and an object at x = +50m will be at the right edge of the screen. The orthographic projection matrix takes care of actually turning the range of [-50, +50] meters into (X, Y) pixel coordinates.
If you have an object at x=1500m, and a camera at x=1550m, you need to map the position of the object to the left edge of the screen regardless of which way you slice the problem. The simplest way to achieve this is to simply subtract the camera position from the object position, which leaves you with the object's position relative to the camera (in this case, x = -50m). In that sense, there really isn't such a thing as "moving the camera," because whatever overall transformation you use still have to map the scene to the screen in an equivalent manner. You could encode the transformation in the projection matrix instead of the view matrix, but they're still multiplied together to yield the same final result. Thus, whether you're moving the world or moving the camera is more a matter of semantics than a practical one.
And yes, every single one of the millions of vertices on-screen need to be subject to this transformation. GPUs are designed to take advantage of the fact that transforming all these vertices is a highly parallelizable workload, and are able to do that enormous amount of math in the very short time in between frames.