In two long-duration balloon flights over Antarctica, the BESS-Polar collaboration has searched for antihelium in the cosmic radiation with higher sensitivity than any reported investigation. BESS- Polar I flew in 2004, observing for 8.5 days. BESS-Polar II flew in 2007-2008, observing for 24.5 days. No antihelium candidate was found in BESS-Polar I data among 8.4times 10^6 |Z| = 2 nuclei from 1.0 to 20 GV or in BESS-Polar II data among 4.0times 10^7 |Z| = 2 nuclei from 1.0 to 14 GV. Assuming antihelium to have the same spectral shape as helium, a 95% confidence upper limit of 6.9 times 10^-8 was determined by combining all the BESS data, including the two BESS-Polar flights. With no assumed antihelium spectrum and a weighted average of the lowest antihelium efficiencies from 1.6 to 14 GV, an upper limit of 1.0 times 10^-7 was determined for the combined BESS-Polar data. These are the most stringent limits obtained to date.