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.