The Argentine superstar netted a double, the second of which killed off a potential comeback from the hosts, to break Brazilian icon Pele's record of 75 goals in a calendar year
Xavi put the Blaugrana on the path to recovering from their shock midweek Champions League defeat to Celtic with a sumptuous free kick, and goals from Lionel Messi and Christian Tello ensured a comfortable lead at the break.
The hosts came back out fighting, though, and pulled two back through Michael Pereira and Victor Casadesus. However, Messi once more saved the day as he ensured that Barca's blushes were spared when he slammed in his 76th goal of 2012, breaking Pele's record for strikes in a calender year in the process.
Mallorca set out to stifle the Catalan giants, dropping midfielders back when out of possession to create a wall of bodies in front of their own goal.
In time, Joaquin Caparros' team grew in confidence but were unable to take the chances that came their way. After blazing over from Ximo's cross moments before, Tomer Hemed saw his header turned around the post by a scrambling Victor Valdes in the 22nd minute.
But it proved only to be a brief scare for the Blaugrana as a moment of pure quality saw them break the deadlock. From a central free kick 25 yards from goal, Xavi curled a majestic, pinpoint shot over the wall and into the top-left corner with 28 minutes on the clock.
Barca should well have had a second five minutes later, but Tello put too much power on his square pass across the face of goal and David Villa was unable to divert the ball into the gaping goal.
Tito Vilanova's men had enjoyed over 70 per cent of possession throughout the first half and they finally put a worthy distance between them and the opposition with two goals in quick succession before the break.
First, Messi was afforded too much space his low shot left Dudu Aouate red-faced as the keeper allowed it to slip through his grasp in the 44th minute. Then, one minute later, Tello received the ball on the left and after cutting in-field onto his right foot, swept a powerful effort past the keeper and into the bottom corner.
Caparros brought Alfaro on in place of Hemed for the second half and the striker almost had the perfect impact. However, he lost his footing when attempting to volley in from close range and ended up sending it over.
Mallorca did get a goal in the 55th minute though as Javier Mascherano was caught in possession by Victor, who then lofted the ball to the far post where Pereira remained composed to fire over Valdes and in.
Three minutes later, the deficit was halved as Victor sent a penalty straight down the middle following a handball from Sergio Busquets in the area.
But Barca used all their experience to take the sting out of the game by holding the ball. They then extinguished any hope of a comeback as Messi rifled in an emphatic second following a brilliant knockdown from Alexis Sanchez.
The Argentine missed a fantastic chance to complete his hat-trick in the 88th minute but it mattered little. The win means the Catalan remain unbeaten in La Liga this season, and temporarily open up a six-point gap over Atletico Madrid at the top.