As the title states: What language was spoken between Mary of Burgundy and Maximilian I. of Habsburg?
I could think of three possibilities: Latin, French and German, but am leaning towards German.
They likely spoke a combination of German and French. It's not entirely clear what they were speaking while teaching their respective mother tongues to each other - most likely Latin, maybe Flemish, maybe some combination of Flemish and German (the two are related enough that you can pick up what was meant every now and then).
Maximilian spoke 6 or 7 languages depending on the source; but not French until Mary taught him. Mary spoke French, Flemish (which is related to German), and Latin; and then learned German.
This article suggests (without sourcing) that:
[Maximilian] spoke seven languages.
Mary taught Maximilian French and he taught her German.
The two claims seem repeated here and there on other sites.
This other article, for instance, offers:
While they could not, at first, speak each other's native languages, they taught each other and communicated well.
Maximilian I of Austria learning the language of Burgundy from his wife Mary of Burgundy. Leonhard Beck, circa 1514 – 1516 | Museum Boijmans Van Beuningen.
This article suggests he spoke six languages.
This last article offers that Mary spoke the two languages of her subjects and Latin:
Mary of Burgundy was an educated woman, in addition to French and Flemish, she knew Latin, studied history.