How much data to use for feature selection?
Have you considered an approach that wouldn't require you to do feature reduction? For example, if you were to use a neural network, the need for feature reduction is greatly reduced. Now, obviously I haven't seen your data so I don't want to suggest that neural networks should be your only answer. But with that many features I would be more concerned with how I'm actually going to reduce them rather than the number of data points that I need to collect.