Desconozco el origen de la palabra (presente en el diccionario desde 1927 con el significado de "caramba"), pero puedo darte una suposición. Iba a escribir esto como comentario, pero creo que puede ser una explicación plausible. Desde 1884 existe en el diccionario de la RAE la palabra:
chis
Voz onomat.
- interj. U. para llamar a alguien.
- interj. coloq. chitón. U. acompañada con algún ademán, como el de poner el dedo índice en los labios.
"Chitón", por supuesto, es una "interjección usada para imponer silencio". Luego es muy probable que el origen sea sencillamente un diálogo de este tipo:
—¡Me ca...!
—¡Chis!
Y simplemente a partir de ahí la expresión se abreviara en "mecachis", ya que uno mismo se mandaba a callar al intentar decir la expresión. En el fichero general de la RAE, si se busca "mechachis", la ficha 13 (PDF), registrada en 1924, parece confirmar mi teoría (al menos, la parte del "me ca..."):
Es una de tantas voces hipocritonas, eufemismos con que se terminan voces mal comenzadas [...]. ¡Mecachis! nació de la locución me ca... amputada antes de terminar puercamente, y trocado su final en chis, dando origen a un vocablo sin sentido castellano.
Esta otra ficha (PDF) lo registra separado ("me cachis"). Otras fichas recogen expresiones como "mechachis en dies/diez". Por último, existe otra palabra con la misma terminación, usada como interjección en Guatemala y que podría tener un origen similar: puchis ("usada para expresar sorpresa o susto").
Como añadido, comentar que los primeros casos que encuentro son de 1870, en la hemeroteca de la Biblioteca Nacional de España. Nótese la expresión escrita por separado y con cachis en cursiva:
—¡Cielos! añadió la duquesa estremecida.
—¡Me cachis! debió añadir Víctor Manuel aparte.
Gil Blas (Madrid). 13/1/1870, página 1.
Es claro; ¿cómo habia de tener fondos el clero para hacer funciones de iglesia, si los necesitaba para hacer funciones de pólvora?
¡Me cachis en esos curas!...
La Iberia (Madrid). 30/4/1870, página 4.