Look at the find command.
What you are looking for is something like
find . -name "*.xls" -type f -exec program
Post edit
find . -name "*.xls" -type f -exec xls2csv '{}' '{}'.csv;
will execute xls2csv file.xls file.xls.csv
Closer to what you want.