How did people figure out the formula for mechanical work, and related it to energy?

What developments led to the definition of Work as the dot product of Force and Displacement vectors?

I did some searching but couldn't find a satisfying answer. According to what I have read, the initial concept of work was associated with measuring work by horses. How did it get associated with energy? Another common answer I got was that "work indicates a transfer of a quantity that happens to be conserved in closed systems just like momentum". I see what that means but how can anyone, possibly, come up with a formula as $$W=F\cdot S$$ from that (or anything else?).

Also, did conservation of $$mv^2$$ in elastic collisions led to development of work formula and modern concept of energy.

It was a side effect of the vis viva controversy described in What was the vis viva controversy, including its philosophical aspects? about what to call the "quantity of motion", momentum (vis mortua, dead force) or kinetic energy (vis viva, living force). Since the conservation of $$mv^2$$ in elastic collisions led to singling out vis viva as a useful concept one could say that it played a part in relating it to mechanical work, indirectly. Other concepts and interrelations in mechanics were also clarified in the course of this "debate about words" resulting in the classical presentations of mechanics by Euler and D'Alambert that we are used to.
Without taking a position on the definition of force, Boscovich measured the velocity acquired as a ratio composed of the pressure and its duration. A geometrical image is generated by the line representing the pressure with time as the second dimension of the diagram. The pressure is thus a function of time. Interpreting this in modern terminology, the momentum $$mv$$ would be represented as the integral of these instantaneous pressures (or impulses) over a time, or $$\int mdv = \int pdt$$.
Boscovich suggested that, if the time coordinate is replaced by the space traversed and the pressure coordinate by the force which at any instant produces the velocity proportional to it, a second aspect of the phenomenon is represented. Boscovich, however, explained neither this substitution nor the introduction of the concept of force. The new term 'force' must be interpreted as an entity proportional to the velocity engendered at any instant. If the pressure coordinate is changed to the force and the time coordinate to the space then the new geometrical image producing the velocity would be represented in modern notation as $$\int Fds$$. We would then interpret vis viva as $$\int mvdv = \int Fds$$ (where $$ds=vdt$$). Boscovich does not bring the mass into this analysis.