Strong magnetic fields in magnetospheres of neutron stars (especially magnetars) and other astrophysical objects may release their energy in violent, intense episodes of magnetic reconnection. While reconnection has been studied extensively, the extreme field strength near neutron stars introduces new effects: synchrotron cooling and electron-positron pair production. Using massively parallel particle-in-cell simulations that self-consistently incorporate these new quantum-electrodynamic effects, we investigate relativistic magnetic reconnection in the strong-field regime. We show that reconnection in this regime can efficiently convert magnetic energy to X-ray and gamma-ray radiation and thus power bright high-energy astrophysical flares. Rapid radiative cooling causes strong plasma and magnetic field compression in compact plasmoids. In the most extreme cases, the field can approach the critical quantum limit, leading to copious pair production.