In both etymological dictionaries that I have available (one of them here; as well as Kluge, 24. edition), it is mentioned that Mitternacht is derived from prepositional phrases that were used as adverbials.
In Middle High German there seems to have been an adjective mitt(e) whose strong (used without article) dative singular feminine form was formed by means of an er-suffix just as in Modern Standard German. From expressions such as Middle High German ze mitter nachte, lit. 'at middle night', middle corresponding to an adjective in the MHG constructions (unlike English where it just occurs as a noun), the noun Mitternacht was derived by dropping the preposition.