On the Great River, after the first ambush by Orcs (which doesn't appear in the movie) and after Legolas shoots down the Nazgul's Fell Beast (likewise), we have the following exchange (the conversation opens with Sam):
'Well, I can remember three nights there for certain, and I seem to remember several more, but I would take my oath it was never a whole month. Anyone would think that time did not count in there!'
'And perhaps that was the way of it,' said Frodo. 'In that land, maybe, we were in a time that has elsewhere long gone by. It was not, I think, until Silverlode bore us back to Anduin that we returned to the time that flows through mortal lands to the Great Sea. And I don't remember any moon, either new or old, in Caras Galadhon: only stars by night and sun by day.'
Legolas stirred in his boat. 'Nay, time does not tarry ever,' he said; 'but change and growth is not in all things and places alike. For the Elves the world moves, and it moves both very swift and very slow. Swift, because they themselves change little, and all else fleets by: it is a grief to them. Slow, because they do not count the running years, not for themselves. The passing seasons are but ripples ever repeated in the long long stream. Yet beneath the Sun all things must wear to an end at last.'
'But the wearing is slow in Lórien,' said Frodo. `The power of the Lady is on it. Rich are the hours, though short they seem, in Caras Galadhon, where Galadriel wields the Elven-ring.'
Aside from that, there are plenty of other occasions where Frodo and Legolas were together and clearly had opportunity for conversation, but what they may or may not have said is unrecorded; here I give just two as examples:
- During Frodo's watch in Moria he first sees Gollum (or at least what can be deduced to be his eyes); Legolas takes the next watch.
- On entering Lorien and after being waylaid by the Elves, Frodo and Legolas are the first two to climb up a flet, and they climb up together.
Despite the fact that any conversation is unrecorded, that doesn't mean that it didn't happen (absence of evidence is not evidence of absence) and it would be very odd indeed if they didn't talk at least for the first of these examples.