In addition to the physical position meaning, "over" has a number of nonphysical and temporal meanings including "again". My own examples:
I couldn't read your note. Write it over.
Take one turn only, no do-overs.
Examples from oxforddictionaries.com:
Used to express repetition of a process: "twice over"; "the sums will have to be done over again"
Most of the other senses listed there seem related etymologically to either "on top of" or the idea of traversal, which are corroborated by Etymonline to share a single root. Intuitively, I can see a connection between these two ideas in the concept of coverage, which could entail being above something and able to exhaustively view or travel across it.
Is the "again" meaning of the word derived from the same core concept (putatively "coverage"), or is it distinct etymologically?
My conjecture: I can contrive a connection from "go over" meaning "review" - retaining the sense of traversal - to "do over" by analogy, meaning generally repeat a process, to detaching the word "over" to be used generally for repetition.