Geological carbon dioxide (CO2) storage is a means of reducing anthropogenic emissions. Dissolution of CO2 into the brine, resulting in stable stratification, increases storage security. The dissolution rate is determined by convection in the brine driven by the increase of brine density with CO2 saturation. We present a new analogue fluid system that reproduces the convective behaviour of CO2-enriched brine. Laboratory experiments and high-resolution numerical simulations show that the convective flux scales with the Rayleigh number to the 4/5 power, in contrast with a classical linear relationship. A scaling argument for the convective flux incorporating lateral diffusion from downwelling plumes explains this nonlinear relationship for the convective flux, provides a physical picture of high Rayleigh number convection in a porous medium, and predicts the CO2 dissolution rates in CO2 accumulations. These estimates of the dissolution rate show that convective dissolution can play an important role in enhancing storage security.