Nat King Cole, 1945:
But what is frim fram sauce, you ask? Or, for that matter, oss'n'fay - or shafafa, on the side? Wiki spells it out for the slow-witted amongst us:
The narrator speaks to a waiter in a restaurant, as if in the process of ordering food. Throughout the song, the customer lists numerous real foods that he doesn't want, such as pork chops and fish cakes. In the chorus, he explains what he really wants: some "frim fram sauce" with the "oss and fay" and "shifafa" on the side. At the end, the narrator character says: "If you don't have it, just bring me a check for the water!" This may be interpreted as, the character was performing a scam: he wanted the water (which is customarily served free to customers at restaurants before they order), and makes up nonsense words for dishes as he has no intention of really ordering anything (which he would have to pay for), and he knows that he will not be charged for the water.
William Safire tries to dig deeper:
Frim fram is one of the oldest terms surviving as slang, cited in John Heywood's 1546 book of proverbs: "She maketh earnest matters of every flymflam" about a woman easily deceived. Flimska is "mockery" in Old Norse, and flim "a lampoon". Thus, as sung by Cole and [Diana] Krall half a millennium later, "frim fram sauce" is the oleaginous goo of deceit poured over some unsuspecting dupe.
Next: ussin-fay is pig Latin for fussin' (just as ixnay conceals "nix"), which in turn has a slang sense of "playing about fretfully"; a whimpering infant is said to be fussin'. This locution seems out of place in a menu metaphor, but I can think of no other logical etymology.
Shafafa is a problem; it is too far from "alfalfa", and no slang term or Old Norse derivation offers a clue. I called Diana Krall and asked if she had any idea about what it meant or where it came from. "It's all about sex," she replied innocently. Oh. That would explain the lyric's "never satisfied", as well as its sauce of deceit, and supply another entendre to the fretful whimpering of fussin'.
Lovely touch with the man seeing himself on the juke-box there - and the unabashed ogling of legs. And, of course, that voice.