Can one perform Feature Selection on a subset of training data?
After finding THE best subset doesn't make sense. Your approach is not correct in this way.
If you cannot handle all data you may have to follow one of approaches below:
1- Perform clustering and chose 10% (the more the better, based on what your computer can handle) from each cluster so all 10 subsets may have similar distribution. As a result, the models theoretically should have similar performance. This approach is useful if you can find clusters in your data. Don't forget to split each subset to training/test subsets!
2- If no clusters found, develop 10 models for each subset and use the average of outputs (bagging), and see how it works.
Hyper parameter tuning is an expensive task, even for small datasets; so it may not be a good idea to do it using not 100% but 70-80% of your data as the training set.
Another thing that you should consider is the ML algorithm you choose. Random Forest may or may not be a good choice. So try different algorithms on small subsets to have an idea which algorithm may work better for your problem. Then think about hyper parameter tuning and feature selection.