When CO2 is injected in saline aquifers, dissolution causes a local increase in brine density that can cause Rayleigh-Taylor-type gravitational instabilities. Depending on the Rayleigh number, density-driven flow may mix dissolved CO2 throughout the aquifer at fast advective time-scales through convective mixing. Heterogeneity can impact density-driven flow to different degrees. Zones with low effective vertical permeability may suppress fingering and reduce vertical spreading, while potentially increasing transverse mixing. In more complex heterogeneity, arising from the spatial organization of sedimentary facies, finger propagation is reduced in low permeability facies, but may be enhanced through more permeable facies. The connectivity of facies is critical in determining the large-scale transport of CO2-rich brine. We perform high-resolution finite element simulations of advection-diffusion transport of CO2 with a focus on facies-based bimodal heterogeneity. Permeability fields are generated by a Markov Chain approach, which represent facies architecture by commonly observed characteristics such as volume fractions. CO2 dissolution and phase behavior are modeled with the cubic-plus-association equation-of-state. Our results show that the organization of high-permeability facies and their connectivity control the dynamics of gravitationally unstable flow. We discover new flow regimes in both homogeneous and heterogeneous media and present quantitative scaling relations for their temporal evolution.