The Argentina forward struck twice for Barcelona to lead 2-0 against Real Betis by the 25th minute of the Spanish league match.
Barcelona's eighth win in as many away games this season puts it six points ahead of Atletico and 11 in front of defending champion Real Madrid.
"As I have said many times, the record is nice but the important thing is the victory that keeps us on the patch we want to continue on," said Messi, adding that he isn't interested in amassing more individual records. "As I always say, my objectives are on a team level: to win the league, the Champions League and the Copa del Rey again."
His first was an individual effort in the 16th minute to equal Mueller's mark, and he eclipsed the 1972 milestone with a familiar left-footed finish nine minutes later.
Messi has scored 74 goals for Barcelona and 12 times for Argentina this year, and he has three more games in which he can add to his tally before the end of the year. Muller scored 85 for Bayern Munich and West Germany.
The 25-year-old Messi passed Brazil great Pele's single-season milestone of 75 goals for Brazil and Santos in 1958 with his 75th and 76th goals of the year on Nov. 11 to move into second place behind Mueller.
After his record 50 goals in the Spanish league last campaign, Messi has led Barcelona to the best start in the history of the championship this season with 13 wins and a draw after the opening 14 rounds. The scoring ace has found the net 30 times already this season in all competitions for Barcelona.
Messi, who became a father for the first time on Nov. 2 to a baby boy named Thiago, was announced as one of the three finalists for the FIFA world player of the year award along with teammate Andres Iniesta and Real Madrid forward Cristiano Ronaldo.
Messi has won the Ballon d'Or award for the past three years in helping Barcelona win three Spanish league titles and two Champions League crowns, along with various other competitions. He is seeking to become the only player to win the award for a fourth time when the winner is announced in Switzerland on Jan. 7.
Nicknamed "The Flea" for his small stature and uncanny ability to slice through defenses, Messi has shattered several records during the past year.
He scored an unprecedented 73 times in all competitions for Barcelona last season, breaking the previous European club record of 67 goals set by Muller in 1972-73 and the prior world club mark of 70 established by Archie Stark of Bethlehem Steel in the American Soccer League in 1924-25.
Fittingly, Messi scored his 73rd and final goal of the 2011-12 season as Barcelona beat Athletic Bilbao 3-0 in the Copa del Rey final in May to give then-coach Pep Guardiola his 14th title in his final game.
In March, Messi passed Cesar Rodriguez's 57-year-old milestone of 232 goals to become Barcelona all-time leading scorer. He also equaled the record of 14 goals in a single European Cup competition last season, scoring five times in one Champions League match to set yet another mark.
- As everyone knows, Lionel Messi has surpassed one of the great records of all time, a mark few soccer fans ever thought would be broken: He has set the all-time record for goals in a single calendar year. But who are the men Messi surpassed on the way to the top? With the various leagues around the world -- and the sometimes shoddy scorekeeping that attends them -- that list has been hard to compile. But after hours of research, here is a confirmed list of the most prolific goal scorers in a single year. Photo: Getty/AP
- With two goals scored against Real Betis Sunday, Lionel Messi broke Gerd Muller's 40-year-old record for goals scored in a calendar year. Messi now has 86 goals in 2012, one more than Muller scored in 1972. He has scored 74 goals for Barcelona, and 12 for the Argentina national team. Photo: Getty Images
- Gerd Muller (left) was a scoring machine for Germany, tallying 572 goals in only 669 matches. But it was his 1972 year that Messi was chasing, when 'Der Bomber' scored an incredible 85 goals in all competitions, including 67 in Europe, a record Messi already broke with his 73-goal campaign in La Liga. Photo: Getty Images
- Messi already eclipsed the second-greatest goal-scoring year of all-time, Pele's 75 goals in 1958, when 'O Rei' was all of 18. Pele's 58 goals that year with Santos remain a tournament record. Not to be outdone, Pele also scored 72 total goals in 1965, 65 in 1959 and 62 in 1961. Photo: AP in English
- Cristiano Ronaldo had a year to remember in 2011, scoring 60 goals in all competitions and helping Real Madrid win the La Liga title. Photo: Getty Images Ronaldo's 2011
- Messi makes the list for the second time after scoring 59 goals in all competitions in 2011 for Barcelona and Argentina. Photo: Getty Images
- Josef Bican, a Czech-Austrian forward who played in the 1930s, scored 57 goals in 24 matches in one year in the Czech League in 1944. He is also considered the most prolific goal scorer of all time with more than 800 goals in competitive matches. Photo: Guardian.com Bican's goal-scoring record