In both cases, the actual reading from the sensor is done line by line. It's done that way (largely) because doing otherwise would be excessively expensive -- to read all the pixels in parallel, you'd need a separate connection from the sensor to memory for each pixel. 12 million connections (for example) from sensor to memory would be horrendously expensive -- and almost never provide any real benefit.
As to why there appears to be a difference between movie mode and still mode, it's pretty simple: in still mode, you're using a physical shutter, and the read-out from the sensor to memory happens when the shutter is closed. As @Matt Grum pointed out, you still get some of the same effect above the X-sync speed, due to physical limitations on the shutter.
The reason you don't use the physical shutter in movie mode is more of those same physical limitations. While the shutter can have a very short exposure time, there's a recovery time between activations, so it becomes difficult to achieve more than about 10 frames per second or so. Getting to the 24 frames per second or so needed for video would, again, add a lot of expense with little benefit. Therefore, in movie mode the physical shutter remains open, and the camera uses an electronic shutter instead -- and once it does that, artifacts of the line-by-line readout from the sensor to memory can become visible.