It's true that it would be extremely unusual for a word to be derived from a perfect stem in Latin, so I feel you're right to be suspicious of Varro and L&S. You're also right to connect it to lēgāre instead, but not in the sense that collēga is derived from it; both must instead be denominal derivations from lēx 'law'. This is also what De Vaan says:
The semantic reasoning for lēgāre seems to be that someone is sent (or something is assigned) in an official capacity under the law, while in the case of collēga it's that someone is bound by the same laws or customs as you.
That said, lēx must be related to legere, so why isn't it a problem that it has a long vowel?
De Vaan, though he doesn't spell it out, seems to see it as a vr̥ddhi derivative, in which the root is put in the lengthened grade to create a related noun: PIE *leg̑- 'to gather' → *lēg̑-s 'related to gathering → a collection (of customs?)'. This same construction of a root noun in a lengthened grade is seen in vōx < PIE *u̯ōkʷ-s from *u̯ekʷ- 'to speak' (in the o-grade, however), and rēx < *h₃rēg̑-s, from *h₃rēg̑- 'to right'.
Vr̥ddhi wasn't available as a productive derivational mechanism in Latin or even Proto-Italic, so these coinages must have happened very early; indeed, for vōx and rēx we know they must be of PIE date because we have Sanskrit वाच् vāc and राज् rāj (Greek ὄψ might be secondarily shortened, but it's probably just a normal non-vr̥ddhi root noun instead).
Another possible explanation is Lachmann's law, which says that when a root-final voiced stop is devoiced before a following voiceless segment, the preceding vowel is lengthened. Lēx has a g at the end of its root, which devoices before the nominative ending -s: PIE *leg̑-s > *leg-s > Latin lēk-s. The fact that the oblique stem also has ē despite no devoicing happening there (gen. lēgis &c.) must then be the result of analogical levelling. In this view lēx was originally just a normal root noun with a regular e-grade, which is generally more common than vr̥ddhi derivatives.
(Lachmann's law is also why the perfect passive participle of lĕgere is lēctus, not lĕctus, and analogy with that is probably why the perfect is lēgī, which, like many Latin perfects, is otherwise hard to explain.)
Either way, neither of these reasonings can apply to collēga directly: collēga is clearly of post-PIE date when vr̥ddhi wasn't a thing anymore (the prefix con- is very Latin), and Lachmann's law can't apply because there's no devoicing of the g. It must be a secondary formation, and the only source that makes sense to me is lēx.
