Right click on the Video folder in the User folder, go to properties, select the location tab, browse to where you want the videos to now be stored. It will ask if you want to move all the files in it. Click yes and done.
You can do this for pretty much ANY of the folders in the User folder.