How to uninstall Windows Mail?

Windows Mail is a Windows system component and cannot be uninstalled or removed, so Microsoft has not supplied any means for that.

To remove, try renaming WinMail.exe to something else, found in C:\Program Files\Windows Mail. You might first use autoruns to see if it's set to start automatically with the computer.

If all you want is to disable WinMail, see details in the article :
How to Enable or Disable Windows Mail in Vista.

The procedure is to open the Local Group Policy Editor -> Computer Configuration -> Administrative Templates -> Windows Components -> Windows Mail, right-click on "Turn off Windows Mail application" and click on Properties, then select "(dot) Disabled or Not Configured" and click OK.

The OP's question was how to remove WinMail from a computer. The other suggestions will disable or only rename the file. If you want WinMail permanently gone from your system, this simple BAT file will do it:

:: Take ownership of the folders
TakeOwn /F "C:\Program Files\Windows Mail" /R /D Y
TakeOwn /F "C:\Program Files (x86)\Windows Mail" /R /D Y

:: Grant full control to Administrators, the user running this, and SYSTEM
ICACLS "C:\Program Files\Windows Mail" /T /Grant:R "Administrators":(OI)(CI)F
ICACLS "C:\Program Files\Windows Mail" /T /Grant:R %UserDomain%\%UserName%:(OI)(CI)F
ICACLS "C:\Program Files\Windows Mail" /T /Grant:R "SYSTEM":(OI)(CI)F
ICACLS "C:\Program Files (x86)\Windows Mail" /T /Grant:R "Administrators":(OI)(CI)F
ICACLS "C:\Program Files (x86)\Windows Mail" /T /Grant:R %UserDomain%\%UserName%:(OI)(CI)F
ICACLS "C:\Program Files (x86)\Windows Mail" /T /Grant:R "SYSTEM":(OI)(CI)F

:: Unhide WinMail.exe
Attrib -S -H "C:\Program Files\Windows Mail\WinMail.exe"
Attrib -S -H "C:\Program Files (x86)\Windows Mail\WinMail.exe"

:: Delete the WinMail folders
RD /S /Q "C:\Program Files\Windows Mail"
RD /S /Q "C:\Program Files (x86)\Windows Mail"