Why is work equal to force times displacement? This is how I think of what work is.I am sure I am wrong somewhere because I shouldn't be coming to the conclusion that I am coming to.It would be helpful if you would point out where this conceptual misunderstanding is.
Work is just change in the energy of an object.The only way an object can gain energy is by movement.Basically if an object's velocity increases then we can say that work has been done on the object.So, work done on an object is directly proportional to the change in its velocity.Also, if the object's mass is high, then for a given change in the objects velocity, the object gains more energy than an object with lower mass, because higher the mass more will be the momentum it can transfer to other objects  and therefore higher the mass of the object for a given change in velocity, more is the work done on the object.Therefore work done is directly proportional to the mass of the object.
I don't seem to find any other factor that influences the work done on an object .Hence according to me work should be equal to mass times the change in velocity.
 A: Realising that there is a connection between two properties does not automatically mean that this connection must be direct proportionality. Couldn't the connection be, say, quadratic?
And that is actually the case. Work $W$ done equals kinetic energy $K$ gained (if we start at $v=0$):
$$\require{cancel}W=K=\frac12 mv^2\qquad\text{ so } \qquad W \propto v^2\qquad\text{ and not }\qquad W \cancel\propto v$$
You are right that it is also true that: $W\propto m$, if we keep the speed constant.
This is not generally the case, though. This is only the case when the object is free to move, so work done only is converted into kinetic energy. If you push a stone up a hill, you can push at constant speed without any gain in kinetic energy - but you are certainly doing a lot of work.
What is the work equal to now? Sure, it is equal to the kinetic energy that would have been gained by the stone if it was free to move (with no friction, gravity etc.). But that is not useful in this case. We can't measure a speed that isn't there. We need another expression for work as well.
It turns out that such other expression is $$W=F\Delta x$$
Both expressions for work can be true at the same time - and they are not both useful in all situations.

*

*The work-energy theorem that states $W=\Delta K$ is only useful if no other energy convertions are involved. (If others are involved, then try setting up the full energy conservation equation.)

*The formula $W=F\Delta x$, or more generally $W=\vec F\cdot \mathrm d\vec x$, is always true but only useful if you know the displacement (the path) and the force at every moment along that displacement.

A: The units of F.ds are those of energy, to start with.  But the "why" is a matter of observations, experimant.:

Work is closely related to energy. The work-energy principle states that an increase in the kinetic energy of a rigid body is caused by an equal amount of positive work done on the body by the resultant force acting on that body. Conversely, a decrease in kinetic energy is caused by an equal amount of negative work done by the resultant force.
From Newton's second law, it can be shown that work on a free (no fields), rigid (no internal degrees of freedom) body, is equal to the change in kinetic energy (KE) of the linear velocity and angular velocity of that body,

Italics mine. Note the term "principle"  and the term "law" . Laws, principles, postulates are the physics axioms necessaryin order to pick up from the mathematical solutions those solutions that describe the data and also are predictive.
So the answer is that the classical mechanics model works in describing accurately data and observations, and in being predictive ( important , otherwise it is not a theory of physics, but a map). That's the way nature is,the work energy principle is axiomatically assumed in order to model the data with the classical mechanics equations.
A: Let me not answer this question but only provide you with a hint. You are already close to what you are looking for.
I don't think that your approach is flawed. There are just a few gaps that you have overlooked. You are right in concluding that the work $W$ should depend on the mass $m$ and the velocity $\vec{v}$. However, you know that $W$ is a scalar. Therefore, it should depend not on $\vec{v}$ but $|\vec{v}|$ or even $|\vec{v}|^2 = v^2$. A quantity that depends on just $m$ and $v^2$ is kinetic energy. You can now start exploring if work is related to change in kinetic energy.
A: This is a rare case where it may help to get more technical. Work is the dot product of the force vector and the displacement vector, and it can be defined as follows $$\vec{F}\cdot \vec{d} = |F||d|cos(\theta)$$
Intuitively, it wouldn't make sense to say that an upward force is causing a box to move horizontally across a room (mathematically that would mean the angle is 90, and the cosine term is zero, making everything else zero along with it), so essentially this dot product is telling us not only what the product of the force and the displacement are, it's also quantifying for us how much that force is responsible for the displacement being seen.
The next part of your question deals with why we see a $v^2$ in the work-energy theorem as opposed to just $v$. Unintuitive as it may seem, it will help to start from the beginning. A displacement implies that we've let time pass for the displacement to happen. During that time, a force acting on a box will change the velocity of the box (an acceleration). But we want to find out how much the distance from the starting point changes since our equation for work depends on displacement, and we can figure this out, but now we can see that we aren't just dealing with the simple factor of $v$, rather, how a changing factor $v$ affects the displacement.
Proving the work-energy theorem to show precisely how the $v^2$ term arises will involve some mathematics, but hopefully this explanation proved why it's not just a factor of $v$.
A: About work:
Let me begin with a little bit of history. James Prescott Joule did experiments along the following lines. He would have a calorimeter, with paddles inside so that moving the paddles would churn the water inside, and the friction of that churning would raise the temperature of the water. One of the ways of driving the paddles would be to have a weigth suspended on a string, and the string running over a pulley so that the weight descending would drive the paddles.
As we know: the outcome of those experiments was that the temperature rise of the water is proportional to the height over which the weight descended.
Let's say that Joule tried two different heights, say 1 meter height and 4 meters of height. (Yeah, you see a squaring coming) 
4 times the height gives 4 times the amount of energy transfer to the water in the calorimeter.
Also, Joule verified that the amount of energy transfer is independent of how fast or how slow the weight descends. The weight can drop fast or slow, at the end the same amount of energy is transferred.
To find a relation with velocity.  
To find a relation with velocity we compare the case of a weight not suspended, but free falling.
If an object is allowed to free fall it gets to keep all velocity it gains. Presumably in the course of free fall the change of energy is the same as in the churning paddles case.
How much velocity does a weight have after 1 meter and 4 meters of dropping?
For simplicity I set the acceleration to 2 m/$s^2$
With an acceleration of 2 m/$s^2$ after 1 second the distance traveled is 1 meter, and after 2 seconds the distance traveled is 4 meters. That is a quadratic relation
How do the velocities compare after 1 and 2 seconds of time?
As we know with uniform acceleration velocity increases linear with time.
With an acceleration of 2 m/$s^2$ after 1 second the velocity is 2 m/s, and after 2 seconds the velocity is 4 m/s. 
We assume that such a thing as kinetic energy exists. Can we express this kinetic energy in terms of mass and velocity?
It follows logically that if you express kinetic energy in terms of velocity the kinetic energy is proportional to the square of the velocity.
Why is the kinetic energy proportional to the SQUARE of the velocity?
Here is one way of looking at that:
Let's say you shoot a marble into a lump of clay. The amount of damage that the marble does is proportional to the depth that it penetrates into the clay.
Assume that the rate of deceleration is constant. For simplicity let's say that it takes 2 units of time for the marble to travel into the lump of clay and come to a stop. With constant rate of deceleration 3/4 of the penetration distance was travelled in the first unit of time, and 1/4 of the penetration distance was travelled in the second unit of time. At the same time: the marble lost 1/2 of its velocity in the first unit of time, and lost the remaining 1/2 of its velocity in the second unit of time.
What this shows:
when you go fast you travel more distance, so you do more damage, in the same amount of time. Your kinetic energy is the amount of damage that you will do on impact, therefore kinetic energy is proportional to the square of your velocity.
A: If you apply a force F to something initially at rest, and keep the force going over a distance D, the force accelerates the thing to a speed V where VV=2FD/M.
In other words the velocity of the body doesn't rise in proportion to FD, but the velocity squared does.
If you rearrange the last expression you get mVV/2=FD. I.e. the kinetic energy is the work done.
A: Need to address a few of your statements before answering.

Work is just change in the energy of an object.

Work can cause a change in the energy of an object, but it is not the energy change of an object. The change in energy of an object is the sum of the changes in its internal (microscopic) and external (macroscopic) energy. Work is a mechanism for transferring energy between objects. The other principle mechanism is heat. 

The only way an object can gain energy is by movement.

An object can also gain energy by heat.

Basically if an object's velocity increases then we can say that work
  has been done on the object.So, work done on an object is directly
  proportional to the change in its velocity.

Technically you should say that net work has been done on the object if the object's velocity has increased. And since there is an increase in the objects velocity there is an increase in its kinetic energy. This gives us the work-energy theorem: The net work done on an object equals its change in kinetic energy.
The reason for stressing the term "net", is that work can be done without increasing velocity, but not net work. For example, positive work is done by an external force when moving an object at constant velocity against surface friction. But an equal amount of negative work is done by friction taking the energy provided by the external force and dissipating it as heat. So the net work done on the object is zero and there is no increase in velocity.
Now, to answer the question:

I don't seem to find any other factor that influences the work done on
  an object .Hence according to me work should be equal to mass times
  the change in velocity.

Change in velocity is acceleration. Mass times acceleration is force, not energy, per Newton's second law: $F=ma$ where $F$ is the net force acting on $m$. A force does not necessarily involve movement. Push against a wall. You exert a force. The wall does not move. The net force on the wall is zero. You've already stated "The only way an object can gain energy is by movement". Movement results in displacement. So the only way forces can cause an object to gain energy is by causing a displacement of the object.
Bottom Line: Based on your own reasoning, work on an object is force times displacement of the object in the direction of the force.
A: If I understood your deduction: " Hence according to me work should be equal to mass times the change in velocity "
$\equiv dW\propto m dv$
From the definition of elementary work:   $\;\;dW=\vec{F}.d\vec{l}=m\vec{a}.d\vec{l}=m\frac{d\vec{v}}{dt}.d\vec{l}= md\vec{v}.\frac{d\vec{l}}{dt}$
$$dW=m \vec{v}.d\vec{v}$$
Therefore, the deduction is not far from the definition.
A: Ok so your understanding is absolutely correct... while people have given quite a few good answers... I would like to present you my point of view...
$ acceleration = \frac{dv}{dt} $
now $\frac{dv}{dt} $ can be represented as $ \frac{dv}{dx} \frac{dx}{dt} $
$\frac{dx}{dt} = V $
Thereforce $a = v \frac{dv}{dx}$
$ a dx = v dv $
of intergarting with resepect to displacement we get
$v^{2} - u^{2} = 2 a s $  where $s$ is the displacement
Multiply both sides by mass $m$
$mv^{2} - mu^{2} = 2 m a s$
$\frac{1}{2} mv^{2} - \frac{1}{2} mu^{2} = m a s$
$m a s$ is now defined as work $W$
and $\frac{1}{2} mv^{2} - \frac{1}{2} mu^{2}$ is defined as change in kinetic energy KE. This is the derivation of the famous work energy theorem.....I hope this helps you
