difference betwen predicting seen and unseen data
What you want to do in building predictive models , in general , is closing the gap between the loss on seen data ( training data ) and unseen data ( test data ). Increasing the numbers of features will naturally make the hypothesis ( the function that is meant to learn from your training and will receive unseen data ( X ) to predict your target value ( Y ) ) more complex and can fit your training data perfectly at a certain point, BUT there is a thresh-hold ( which you went above according to your results by increasing the number of features) where your model starts giving very good results on your training set and much poorer results on the test set, and that is called overfitting which is a problem caused by high variance in your model which basically means you are allowing your function to be complex enough to fit your training data perfectly, and be less able to predict unseen data ( your test data ). 

Go with the feature selection technique if it reduces the gap between your training loss and test loss!

Notice here in this example that increasing the number of features gives lesser test loss but, at a certain point, the loss on test starts going up again.