There have been a number of multiply-breasted female characters seen in science-fiction and horror films. Be warned, NSFW links below...
Four-breasted characters are seen in;
Six-breasted character are seen in
However, he first appearance of a three-breasted character seems to be Star Trek 5: The Final Frontier from 1989, released over a year before Total Recall.
A cat-like alien woman with three breasts is seen in the cantina scene on Nimbus III.
There's an even earlier match for a three-breasted character in the Sci-horror film "Vicious Lips" from 1986.
A band finally gets the opportunity for that breakthrough gig if they can make it to an "in" club on another planet. They encounter a variety of strange aliens....
I've found an even earlier match in the Sci-smut thriller Galaxina from 1980.
Our (ahem) heroes visit an alien brothel where they encounter many attractive alien females: