At the very latest, when he meets the Red Daughter for the first time.
By the time he meets Eve for the first time (chronologically prior to Season 2) he already knows James Olson is friends with Supergirl.
"Jimmy Olson works there. He's been a thorn, but he's connected to the second Kryptonian."
Season 4, Episode 16, The House of L
When he meets the Red Daughter for the first time, she clearly has still latched on to Alex, and Lex knows this. While he introduces himself as Lex the first time, she calls him Alex and all the letters he sends the Red Daughter are addressed from Alex. There aren't that many people connected to James Olson with that close a connection to Alex.
He probably knew prior to his trial
At Lex's trial, James admits (at the beginning of Season 4, Episode 16, chronologically prior to Season 2) that Lex tortured him. James is a good friend to Superman, but Lex is sly and Superman probably doesn't think his secret identity is worth his friend's life anyway. Once Lex knows Superman's identity it's a pretty simple jump to Supergirl's. In fact,...
Lex may have known as early as Season 1
In Season 1, Maxwell Lord finds out Supergirl's identity. Although he doesn't reveal it to the world, that information might make it's way to Lex Luthor.
Alex: "He knows about the DEO. He knows about Kara."
Season 1, Episode 12, Bizarre
There's also several compromised DEO agents who could have revealed that information. Note that the only group that's really worked to uncover Supergirl's identity and failed is the DEO, and Brainy (the person on their staff who would do the majority of the technical analysis) is actively working to destroy evidence. Lex Luthor investigating at the beginning of Season 1 when Kara is making more mistakes would have a much easier time.