OS X uses HFS+ as the file format for external disks. Note that Apple only supplies read-only drivers for Windows, which means that there's no easy way to write.
However, there are a couple of commercial tools to format as HFS+ using Windows:
TransMac for Windows can open Macintosh format disk drives, flash drives, CD/DVD/Blu-ray media, high density diskettes, dmg and sparseimage files. [...] Format disks for use on Mac
MacDrive™ 8 allows Windows users to open, edit and save files on Mac disks. [...] What if you need to format a Mac disk or create and delete partitions on a Mac drive? You can, using the powerful MacDrive Disk Manager.
Both offer free trials though.
That being said, I don't see why a Mac would be too slow to format a drive. Be on the safe side and just do it on the Mac, even if it takes a while longer.