Does it make sense to randomly select features as a baseline? In my paper, I am saying that the accuracy of classification is $x\%$ when using the top N features. 

My supervisor thinks that we should capture the classification accuracy when using N randomly selected features to show that the initial feature selection technique makes an actual difference. 

Does this make sense?

I've argued that no one cares about randomly selected features so this addition doesn't make sense. It's quite obvious that randomly selecting features will provide a worse classification accuracy so there's no need to show that using any sort of feature ranking metric will be superior.
Your supervisor is asking to use random feature selection as a baseline. Random performance is a common baseline in machine learning. For example in binary classification with equal numbers of samples from each group, a trained classification should perform better than 50% (random guessing).