If you're running retroarch from the command line, try looking in the folder that you're running the program from. So if you cd ~/games; retroarch then your videos will be saved in ~/games.
Also the relevant setting is recording_output_directory (mine was an empty string which is why it was saving to the pwd)