Müller erlernte 1932–1938 den Beruf des Dekorationsmalers und wurde danach zum Kriegsdienst in die Wehrmacht eingezogen. 1943 geriet er in sowjetische Gefangenschaft, aus der er 1945 entlassen wurde. Er wurde dort Mitglied eines antifaschistischen Ausschusses. Anschließend kehrte er nach Halle zurück. 1946–1948 studierte er an der Kunstschule Burg Giebichenstein bei Erwin Hahs. Danach arbeitete er in Halle als freischaffender Künstler. Seine erste Einzelausstellung hatte Müller 1948 im Marktschlößchen Halle. 1947 gehörte er zu den Gründungsmitgliedern der halleschen Künstlergruppe Die Fähre. Ab 1953 bildete er u. a. mit Willi Sitte, Karl Völker und Otto-Heinz Werner (1914–2000) als Form genossenschaftlicher Zusammenarbeit die Hallesche Malerbrigade, die in Vorbereitung der Dritten Deutschen Kunstausstellung in Dresden einem „modernen sozialistischen Realismus“ zum Durchbruch verhelfen wollte.[1] Von 1947 bis 1950 übernahm Müller mit Sitte und Herbert Lange (1920–2001) eine große künstlerische Arbeit im Mansfelder und Bitterfelder Bergbaugebiet. Es folgten zahlreiche Gruppen- und Einzelausstellungen sowie in den Jahren 1966 bis 1983 Studienreisen nach Indien, Sri Lanka, Nepal und Pakistan. Anfang der 1970er Jahre unternahm er mit Rolf Kiy im Auftrag des Mansfeldkombinats eine Studienreise nach Kriwoj Rog.
Müller widmete sich in seinen Werken immer wieder historischen und aktuell-politischen Themen, so 1958 anlässlich eines schweren Bergwerkunglücks in Belgien mit dem Tafelbild Memento Marcinelli (Öl, 150 × 100 cm)[2], 1958 mit dem Grafik-Zyklus Algerien (z. B.[3]) und 1962 mit Le fascisme ne passera pa (Öl, 125 × 250 cm)[4]
Zahlreiche Bilder von Menschen und Landschaften Südasiens kennzeichnen einen unverwechselbaren Abschnitt in seinem Spätwerk.
Müller war bis 1990 Mitglied des Verbands Bildender Künstler der DDR. Er hatte in der DDR und im Ausland eine große Zahl von Ausstellungen und Ausstellungsbeteiligungen, u. a. von 1949 bis 1988, außer 1982/83, an allen Deutschen Kunstausstellungen bzw. Kunstausstellungen der DDR in Dresden.
Darstellung Müllers in der bildenden Kunst
Walter Arnold: Porträt Karl-Erich Müller (Bleistift-Zeichnung, 20 × 30 cm, 1967)[5]
Gerhard Geyer: Maler Karl-Erich Müller (Porträtbüste, Bronze, 1972)[6]
Eberhard Frey:Betrachtungen zum Werk von Karl Erich Müller. In: Bildende Kunst, Berlin, 1957, S. 802–805
Günter Hess: Ein Bonvivant der bürgerlichen Dekadenz. Zu den grafischen Blättern „Felix Krull“ von Karl Erich Müller. In: Bildende Kunst, Berlin, 1959, S. 632–636
Wolfgang Hütt: Karl-Erich Müller als Maler. In: Bildende Kunst, Berlin, 1962, S. 455–461
Wolfgang Hütt (Hrsg.): Karl Erich Müller. 12 farbige Gemäldereproduktionen, 4 einfarbige Tafeln. Henschelverlag, Berlin, 1965 (Reihe Welt der Kunst)
Wolfgang Hütt: Eindrücke von der „First Triennale India“ und das Erlebnis Indien in neuen Arbeiten von Karl-Erich Müller. In: Bildende Kunst, Berlin, 1968, S. 373–378
Ingrid Schulze: Das Indienbild im neueren Schaffen Karl Erich Müllers. In: Bildende Kunst, Berlin, 1973, S. 378–381, 411
Wolfgang Hütt: Karl Erich Müller.Maler und Werk. Verlag der Kunst. Dresden 1973
Ernst-Werner Schulze: Vom Schwejk über Cocqueville zum Krull. Zu Karl Erich Müllers Illustrationen aus den fünfziger Jahren. In: Bildende Kunst, Berlin, 1985, S. 448/449
Müller, Karl-Erich. In: Dietmar Eisold (Hrsg.): Lexikon Künstler in der DDR. Verlag Neues Leben, Berlin 2010, ISBN 978-3-355-01761-9, S. 632/634
Karl Erich Müller: Malerei und Graphik aus drei Jahrzehnten. Ausstellungskatalog, Akademie der Künste der DDR, 1979.
Karl Erich Müller: Erlebnis Südasien. Ausstellungskatalog, Staatl. Galerie Moritzburg, Halle, 1987.
Karl Erich Müller zum 75. Geburtstag: Malerei, Grafik (1987–1992). Ausstellungskatalog, Museum Schloß Bernburg, 1992.
Karl Erich Müller: Klecksographien. Eine Auswahl. Herausgeber Dietmar Petzold für die Burg Giebichenstein Kunsthochschule Halle, 2007
Hans-Georg Sehrt: Karl Erich Müller (1917–1998) – Mit Pinsel und spitzer Feder, Arbeiten auf Papier. Halle (Saale) 2007, 48 S., 36 Abb., hrsg. vom Halleschen Kunstverein e.V. zur Ausstellung vom 12. Mai–15. Juli 2007 im Opernhaus Halle