RouteData also has a constructor that takes no arguments. Simply create one and add the values to it that you want. No need to mock it when you can create one.
var routeData = new RouteData();
routeData.Values.Add( "key1", "value1" );
var controllerContext = new ControllerContext(httpContextMock.Object, routeData, controllerMock.Object);