Nonlinear frequency conversion plays a crucial role in advancing the functionality of next-generation optical systems. Portable metrology references and quantum networks will demand highly efficient second-order nonlinear devices, and the intense nonlinear interactions of nanophotonic waveguides can be leveraged to meet these requirements. Here we demonstrate second harmonic generation (SHG) in GaAs-on-insulator waveguides with unprecedented efficiency of 40 W-1 for a single-pass device. This result is achieved by minimizing the propagation loss and optimizing phase-matching. We investigate surface-state absorption and design the waveguide geometry for modal phase-matching with tolerance to fabrication variation. A 2.0 µm pump is converted to a 1.0 µm signal in a length of 2.9 mm with a wide signal bandwidth of 148 GHz. Tunable and efficient operation is demonstrated over a temperature range of 45 °C with a slope of 0.24 nm/°C. Wafer-bonding between GaAs and SiO2 is optimized to minimize waveguide loss, and the devices are fabricated on 76 mm wafers with high uniformity. We expect this device to enable fully integrated self-referenced frequency combs and high-rate entangled photon pair generation.