Of American-English origin, to play footsie with somebody means:
– to surreptitiously touch somebody’s foot or ankle with one’s own foot, especially under a table at which both persons are sitting, as a playful expression of sexual attraction;
hence also, figuratively:
– to have underhanded dealings with somebody.

(In this phrase, footsie appears in several variants, such as footsies and footsy, and in reduplicated forms, such as footsy-footsy.)

An earlier form, to play footie, or footy, with somebody, is first recorded in The Stolen Apples System, a short story by ‘Achmed Abdullah’, published in The Smart Set: A Magazine of Cleverness (New York, N. Y.) of November 1917*; in this story, the Stolen Apples system denotes a system consisting in a secret love affair with a girl, “away from the protective bosom and the carved golden oak sideboard of her family home”; the following is the conclusion of the story:

At half past ten that evening Cornelius asked Mr. and Mrs. Van Twilliger for the hand of their daughter, and was accepted.
Ten minutes later he was sitting on the couch in the music room, with his arm around Priscilla’s waist.
And, at just about the same time, Mr. Van Twilliger was smoking a cigar in his wife’s boudoir.
“How did it happen, Julia?” he asked, still dazed.
She was in the act of blue-pencilling the column in her account book which was entitled: “Miss Priscilla Van Twilliger.”
“Adrian dear,” she commenced—she blushed, and was silent.
“Tell me, my love, how did it happen? Don’t you know?”
“Of course I know. I did it.”
“You did it? What did you do?”
“I—” again she blushed, then she spoke out bravely. “I—I decided to encourage Cornelius—to—to give him a taste of Stolen Apples. I—”
“Well?”
“I played—footie with him!” She brought out the word as if it choked her. “And he—Cornelius—thought it was Priscilla’s foot!”
And upstairs, in the music room, Cornelius and Priscilla wondered at the peals of laughter which drifted down from Mrs. Van Twilliger’s boudoir.

(* This story was not published in The Smart Set of December 1917, as erroneously stated in the Oxford English Dictionary – 3^rd edition, 2016.)

The earliest instance of to play footsie with somebody that I have found is, with the variant footsies, from the column One Word Led to Another, by the American journalist and humorist Arthur ‘Bugs’ Baer (1886-1969), published on Thursday 25^th May 1939 in several newspapers, for instance in the Stevens Point Daily Journal (Stevens Point, Wisconsin):

Long May They Waver

They say our ambassadors to Europe are being vamped by beautiful princesses. Put in Seven Dwarfs, a bit of technicolor and you have a movie.
It’s nice work if it gets you. There was the same complaint in 1914 about our diplomats in various European districts. But don’t forget that our old pal Ben Franklin was no small shucks at playing footsies under the table.

I have found an early instance of to play footsie with that is interesting because:
– it is not followed by a noun denoting a person, but by a noun denoting an abstract idea,
– and means to toy with, to argue the pros and cons of.
This instance is from The Daily Times (Davenport, Iowa) of Friday 23^rd May 1941:

New York
By S. Burton Keath
Peace

From high British officials, through trustworthy intermediaries, word is reaching New Yorkers that the war’s outcome may be decided within the next few days. The long-run result is conceded to be problematic under the best of circumstances. But it is said flatly that whether Britain can go on after June 30 will depend upon decisions now being made in the White House executive offices in Washington.
President Roosevelt and his most trusted advisers, according to information coming through the best pipelines, at last are facing their ultimate decision. In effect they have posed to themselves one soul-searching question: Can Britain win with our all-out assistance? Or will U.S. belligerency merely prolong the agony, postpone inevitable collapse, and leave us holding the bag? If they decide that there is an outside chance of beating the Axis, it is predicted that Mr Roosevelt will take us into the shooting war suddenly, dramatically and irrevocably.
On the other hand, if the possibility of ultimate success seems too slight to warrant the terrible hazard, and the president decides to procrastinate and dilly-dally and play footsie with belligerency, British informants predict that a negotiated peace will be made in Europe no later than midyear.

In the following instalment of the comic strip Blondie, titled Let’s Play Footsy!, published in the Wisconsin Rapids Daily Tribune (Wisconsin Rapids, Wisconsin) on Monday 10^th March 1947, the American cartoonist Murat Bernard ‘Chic’ Young (1901-73) played on the difference between the usual sense of the phrase and what he depicted:

“Lift your foot, please, dear” | “It’s impossible to read in all that commotion—I’ll go out in the garage” | “Now lift the other foot”

FRENCH EQUIVALENT

The French phrase is faire du pied à quelqu’un, short for faire signe du pied à quelqu’un, to make sign with the foot to somebody.

Two other French phrases referring to playful expression of sexual attraction follow the same grammatical pattern:
– faire du genou à quelqu’un (genou: a knee);
– faire de l’œil à quelqu’un (œil: an eye), meaning to give somebody the eye, to make eyes at somebody.