How did "give up" start to mean to quit?
"Give up" is almost a word-for-word translation of surrender (sur = over/above/up + render = to give, present), so it seems to be an Anglosaxon version of a French/Latin word. It has been used for much longer 400 years but was probably popularised through its use in the King James Bible:
30 When Jesus therefore had received the vinegar, he said, It is finished: and he bowed his head, and gave up the ghost.
John 19:30 King James Version (KJV)
In French, we have the word: "se rendre" = to render itself. Implicitly, it is "to render itself to the winner". To let him/her decide about your future. It is close to the meaning "to abandon" if you think that for many religions your daily life is controlled by destiny (to render itself to destiny is likely a very used concept in old books) and other similar concepts.
I suspect that with the tradition of hiding the reflection in English, "se rendre" turned into "to render/give" and the particle "up" was necessary to explicit a specific meaning, as do all phrasal verbs.
Note also that "surrender" is likely to be the pronunciation of "se rendre" by an English teller. Coincidence or I think not.
Give up is also word to word equivelant of German aufgeben (auf = up, geben = give).
My guess is that in old times, people who didn't make any more active actions in pursuit of their interest, gave the matter up to the deity up above in the sky (i.e. god).
With time the original meaning of giving it to someone/something else was forgotten, and it came to mean only the part of stop actively trying to do something by yourself.