The thing you will need to do here is use a linear gradient as background and animate the background position. In code:
Use a linear gradient (50% red, 50% blue) and tell the browser that background is 2 times larger than the element's width (width:200%, height:100%), then tell it to position the background right.
background: linear-gradient(to left, red 50%, blue 50%) right;
background-size: 200% 100%;
On hover, change the background position to left and with transition:all 2s ease;, the position will change gradually (it's nicer with linear tough)
background-position: left;
http://jsfiddle.net/75Umu/3/
As for the -vendor-prefix'es, see the comments to your question
extra:
If you wish to have a "transition" in the colour, you can make it 300% width and make the transition start at 34% (a bit more than 1/3) and end at 65% (a bit less than 2/3).
background: linear-gradient(to left, red 34%, blue 65%) right;
background-size: 300% 100%;
Demo:
div {
    font: 22px Arial;
    display: inline-block;
    padding: 1em 2em;
    text-align: center;
    color: white;
    background: red; /* default color */
    /* "to left" / "to right" - affects initial color */
    background: linear-gradient(to left, salmon 50%, lightblue 50%) right;
    background-size: 200%;
    transition: .5s ease-out;
}
div:hover {
    background-position: left;
}
<div>Hover me</div>