I suspect that uh-oh was used in speech long before it was spelled in that form. The problem is that its probable written antecedent, "oh-oh" or "oh, oh" only sometimes represents the speech pattern "uh-oh"; at other times it signifies a repetition of the one-syllable word (or exclamation) "oh." In any case, if "oh oh" was the predecessor of "uh-oh," it would be difficult to isolate the instances where the intended pronunciation and intonation matched those of the later spelling.
Antecedents aside, a Google Books search does find instances of uh-oh (with or without the hyphen) in the relevant sense from considerably earlier than 1971. In this answer I focus on instances prior to 1965.
From Langston Hughes, Little Ham (1935), reprinted in Five Plays by Langston Hughes (1963):
MADAM [BELL] Yes, darling, let's go. (They start toward the door, but MADAM BELL suddenly pauses as MATTIE BEA enters. Excitedly) Look, LeRoy, there's Ham's other woman! Uh-oh!
LEROY Who? Where? Which one?
MADAM (Pointing) Mattie Bea!
LEROY Uh-oh! Watch out!
From a series of copyright entries for commercial prints submitted by Freithofer Baking Co. of Philadelphia, in Catalog of Copyright Entries. Part 4. Works of Art, Etc. New Series (1943):
Uh-oh! Newlywed in distress! © Nov. 30, 1943; KK 17998.
Uh-oh! The fateful dawn. © Nov. 25, 1943; KK 18000.
An index entry in Catalog of Copyright Entries: Musical Compositions (1945) includes this bare-bones data on a song title and citation number: "Uh-oh. 62772."
From an advertisement for Arrow Shirts in Life magazine (December 9, 1946):
JEAN: He's in a new show—opens tomorrow night. And he said he'd get us two tickets, first row center, if—
BILL: Uh-oh. Now I catch on—
JEAN:—if I could possibly persuade you to let him have one of your new Arrow white shirts. Will do?
BILL: O. K., honey, I guess Pretty Boy can have it. But opening night only. Then I want my Arrow back!
From Joseph Mitchell, Old Mr. Flood, (1948):
He [a deckhand] marched up the dock, drumming on the bucket and yodeling, stepping high, a regular one-man band. Another one turned a double somerset and stood on his head right on the edge of the dock. He got up, shook himself and began to sing song called 'Tiptoe Through the Tulips with Me.' 'Uh-oh!' I said to Drew. 'The oysters have caught up with them.'
From Saul Gottlieb, "A Mythical Merry-Go-Round: A Fantasy for Radio," in Generation (Summer 1950):
ALLEN: They're putting out the brass rings, Lucy—make a grab for it!
LUCY: Uh-oh, I missed it!
ALLEN: You couldn't catch a cold. Watch me.
LUCY: There—you missed too.
From David Dunbar, "Family First Aid," in Boys' Life (June 1951):
Wait a minute, Sis! That water is hot stuff, an the pan is too heavy for you. Uh-oh, we're too late. Sis thought she'd help Mom with lunch, but she wasn't careful enough, her arm was burned by the hot water.
From "The Play Goes On and On," in Boys' Life (March 1952):
"You know, Spiffy is really a swell person," she said enthusiastically. "And he's nobody's dumbbell either. It didn't take him long to figure out how well he fitted that part. And it worked out just like in the play. He's got a lot to learn but he's getting there. Poor guy. He's never had any friends and he was really lonely. Guess what? He was actually scared stiff I wouldn't come to the party with him tonight!"
"Uh-oh," chortled Peeps, "so the play must go on and on and on."
From Ted Friedman, "Genie in the Bottle," in The Michigan Technic (April 1956):
Before he could finish, the electric typewriter began clattering.
"Uh-oh, something's up."
Joe ran over to the typewriter and read the message.
Chart Book, volume 63, issue 11 (1958), reports three races run by a horse named "Jeff's Uh Oh."
From an advertisement for ChapStick in Life magazine (February 2, 1959):
UH-OH! watch those lips! What's in the wind?—trouble, plenty of trouble for lips exposed to wind and cold and sleet.
Billboard magazine (January 11, 1960) reports that on that date the Nutty Squirrels had two hit singles in the Billboard Hot 100 pop records chart: "Uh! Oh! (Part II)" at number 24, and "Uh! Oh! (Part I)" at number 84. Billboard further reported that "Uh! Oh! (Part II)" had been on the chart for ten weeks and "Uh! Oh! (Part I)" for six weeks. Aside from a few stray English phrases such as "Groovy man," "Far out," and "One more time," both parts of "Uh! Oh!" consist of meaningless scat-singing syllables, as you can hear on this YouTube recording of the songs. Nevertheless, the intonation of "uh! oh!" that the squirrels use is exactly like the "uh-oh" that a parent uses when speaking to a toddler (or vice versa) after a mishap. The Wikipedia article on the Nutty Squirrels states that the band released "Uh Oh" in 1959, which is consistent with the Billboard data.
From Joan Williams, The Morning and the Evening (1961):
There was a fried chicken leg, a stuffed egg, and a piece of marble cake. He ate them all. He was licking his fingers when Sam came back. "Uh-oh," Sam said. "You can't have that." He took the razor.
From "Try These 4-H Song Parodies at Your Next Club Meeting," in National 4-H Club News, volumes 39–40 (1961[?]) [combined snippets]:
(NORTH CAROLINA) Arlita Lowry, Pembroke (Tune: Old McDonald) Mary had an unsafe home,/Me, oh my, oh oh!/And in this home she had frayed wires,/Me, oh my, oh, no!/With a little shock here,/A little shock there,/Here a shock, there a shock,/Everywhere a shock, shock/Mary had an unsafe home,/Me, oh my, oh oh!/(Other verses using "poison drugs—little dose here; throw rugs—little fall here; piled up junk—little fire here; loaded guns—bang, bang here.)/Mary had an unsafe home,/Me, oh my, uh oh!/And in this home they found poor Mary,/Me, oh my, uh oh!/And now poor Mary is no more,/Me, oh my, uh oh!/They found her dead upon the floor,/Me, oh my, uh oh!
From Herbert Simmons, Man Walking on Eggshells (1962):
Class got real quiet. Then the door flew open and Mr. Purcell walked in.
He waved his finger at Carl.
Jerome went Woody Woodpecker and started flapping his arms around when Carl and Mr. Purcell went out the door but class was quiet. Caught at Teacher's desk by the principal, oo-oo-wee!
From Ken Kesey, Sometimes a Great Notion (Viking Press, 1964, but copyrighted by Kesey in 1963):
"Damned if I know. I figured they'd be here waiting. But, now ... what I reckon is, the pack there sounds like it tried once, then headed off again." He frowned, scratching the tip of his nose. "Yeah, ,,, I reckon Molly took the pack off to that bear—uh-oh, hear that? fox is turnin'—and soon as Uncle saw what he'd got into he says, 'Let's go, boys. Leave that fool Molly to get et by a bear if she so wants. Let's go hunt some fox.' ..."
"Hell, boy I don't know why." He tossed a stick into the flames. "You got the education, I'm nothin' but a dumbass logger. I just know that I decided it didn't stand to reason a deer or beer—or say a fox, who's supposed to be a pretty smart customer—would drown hisself just to get shut of a few fleas. That's a purty stiff cure." He stood up and walked a few paces from the fire, brushing the front of his pants. "Uh-oh, listen there ... they cut him off. They got the sucker now if he don't swim."
The word uh-oh has been showing up in print since at least 1935 (when it appeared in a play by Langston Hughes), although it didn't become common in print until the 1960s. The fact that most of the early Google Books matches for the term occur in dialogues or advertising (or both) suggests that "uh-oh" was already well established in speech as an exclamation before it began to make its way into print. That, in turn, raises the possibility that earlier attempts to replicate the expression may have use a different spelling (such as oh, oh) that would be difficult to distinguish from other vocalizations that shared the same spelling.