Как сказал Дарин, вы делаете это в javascript.
Добавьте атрибут id к вашему тегу привязки, чтобы мы могли ссылаться, используя это.
@Html.ActionLink(genre.Title,
"Browse", "Store",
new { Genre = genre.Title, VideoType = }, new { @id="link1"})
Затем, используя javascript, изменитессылка,
$(function(){
$("#VideoType").change(function(){
$("#link1").attr("href")="Store/"+$("#VideoType").val();
});
});