How to compare the performance of feature selection methods?
This is a hard problem and researchers are making a lot of progress.

If you're looking for supervised feature selection, I'd recommend LASSO and its variants. Evaluation of the algorithm is very straightforward with supervised learning: the performance of whichever metric you choose on test data.

Two major caveats of LASSO are that (1) the selected features will not automatically detect an interaction, so you have to craft all of your features a priori (i.e., before running them through the model) and (2) LASSO will not identify non-linear relationships (e.g., a quadratic relationship).

A way to try and get past these two caveats is to use Gradient Boosted Machines which does feature selection automatically. It's worth noting the statistical properties of GBM are a little more ambiguous than that of the LASSO. 

If you're looking for unsupervised feature selection, it seems there's a similar regularization approach used by these researchers, but evaluation in this particular case becomes less obvious. People try a lot of different things like PCA/SVD or K-Means which ultimately will try to find a linear approximation to the data. 

In that case, the typical measures of performance are the reconstruction error or the RMSE of the clusters.

In terms of software, R and Python both have GBM, LASSO, K-Means, SVD, and PCA. GLMNET and XGBoost in R and Sklearn for Python are the relevant libraries.