The etymology provided by the Concise Oxford Dictionary is complex!
Apparently the derivation is from the Old English 'bot' and/or the Old Saxon 'bota', which derive from the Old High German 'buoza', the Old Norse 'bot', and the gothic 'bota'. They, in turn, are derived from the Germanic 'boto', meaning 'remedy', with links to the modern 'better' and 'best'.
So 'to boot' (very roughly) means 'to the better'.