Malborn is supposed to automatically move to a table in a dark corner of the Winking Skeever when you proceed the quest correctly, but if he doesn't, he can probably still be found around town. You may also wish to check the New Gnisis Cornerclub in Windhelm; it's where he tends to go after the quest is complete, and he may have ended up there early by accident.
Alternately, if you are on the PC version, you can try opening the console and typing
This should find Malborn wherever he is and move him to your location.
It looks like Malborn doesn't even exist until the quest; it literally spawns him in as you get the objective, and then attaches the correct scripts. If the
prid command fails, then it's likely that Malborn simply never spawned at all correctly. In that case, you can try either reloading a save from before you talked to Delphine, or try using some combination of
setstage mq201 30
setstage mq201 40
The first will reset the quest to immediately before Delphine tells you to talk to Malborn, the second grants the "Meet Malborn in Solitude" objective. You may just need to run the second, maybe both, maybe just the first, and then talk to Delphine; without my own game showing the same bug, I can't be entirely certain.