What language to use for a total rewrite of a legacy payroll program?

Well that is mostly a question of preference. Usually all Languages with some C interface allow easy access to MySQL.
The generators to build screen forms are part of a lot of programming language and have names like Resource Editor or GUI Builder... So you could use among others
- Visual C/C++
- Borlands C++ Builder
- Visual Basic
- .NET stuff
- Smalltalk
- Common Lisp
- Delphi
- Java
- and and and

to access Databases on Windows you usually want to use ODBC, or some other abstraction layer like e.g JDBC...

So let us assume you do not want to learn something new. Then you need either a basic, rexx, dbase, C or C++
Because it's used nearly everywhere I suggest you use some tools from Microsoft, it seems the way to go on Windows is with .NET.

The learning curve for MS tools is very different, without beeing extra carful you might get caught in the "just click it together" trap and end with a crude mixture of code for handling the GUI and program logic.

Or check out what path dbase has gone.
http://www.dbase.com/

The requirements are such that a lot of tools are available. So what preferences you have? What system do you plan to run you application on? Have you considered some sort of Web access?  Do you want to extend the program with some sort of scripting? Does it really have to be MySQL? how about some other "heavy weight" DB System?  Maybe you want to migrate you software to something exsiting, because this applications are so common and there are so many alternatives available.

Regards
Friedrich

Have you considered looking at purchasing an off-the-shelf payroll solution. These will tend to be much cheaper in the long run because of the ecomonies of scale etc. and they are tried and tested solutions. Most also provide several API's that can be used for customization and custom reporting functions.