Müller's hat-trick - one a penalty - and goals by Swiss Brendan Shaqiriband Dutch veteran Arjen Robben saw them dispose of their hosts and into Saturday's second round draw.
It gave Bayern and their coach Pep Guardiola an ideal lead in to the opening match of the defence of their league title on Friday at home to Borussia Mönchengladbach, who exited the Cup on Sunday beaten on penalties by Third Division Darmstadt.
Guardiola, whose first competitive match in charge on July 27 saw his side beaten 4-2 by Borussia Dortmund the side they beat in the Champions League final last term, allowed himself the luxury of not starting several first choice regulars such as Franck Ribery and captain Philipp Lahm while new signing from his former club Thiago Alcantara also had to be content with a place on the bench.
Earlier on Monday Schalke had made hard work of beating another fifth division outfit FC Noettingen 2-0, with Dutch ace Klaas-Jan Huntelaar giving them a 30th minute lead but they had to wait till the fourth minute of time added on to double their lead as new signing Leon Goretzka netted.
Schalke despite their unconvincing performance are through to the next round, the matches taking place on September 24 and 25, but three others from the top division joined Mönchengladbach in failing to make it to the second round.
The highest profile casualty apart from Mönchengladbach was Werder Bremen, who went out beaten 3-1 by Third Division Sarrebruck.