We analyze the redshift- and luminosity-dependent sizes of dropout galaxy candidates in the redshift range z~7-12 using deep images from the UDF12 campaign, data which offers two distinct advantages over that used in earlier work. Firstly, we utilize the increased S/N ratio offered by the UDF12 imaging to provide improved size measurements for known galaxies at z=6.5-8 in the HUDF. Specifically, we stack the new deep F140W image with the existing F125W data in order to provide improved measurements of the half-light radii of z-dropouts. Similarly we stack this image with the new deep UDF12 F160W image to obtain new size measurements for a sample of Y-dropouts. Secondly, because the UDF12 data have allowed the construction of the first robust galaxy sample in the HUDF at z>8, we have been able to extend the measurement of average galaxy size out to significantly higher redshifts. Restricting our size measurements to sources which are now detected at >15sigma, we confirm earlier indications that the average half-light radii of z~7-12 galaxies are extremely small, 0.3-0.4 kpc, comparable to the sizes of giant molecular associations in local star-forming galaxies. We also confirm that there is a clear trend of decreasing half-light radius with increasing redshift, and provide the first evidence that this trend continues beyond z~8. Modeling the evolution of the average half-light radius as a power-law (1+z)^s, we obtain a best-fit index of s=-1.28+/-0.13 over the redshift range z~4-12, mid-way between the physically expected evolution for baryons embedded in dark halos of constant mass (s=-1) and constant velocity (s=-1.5). A clear size-luminosity relation, such as that found at lower redshift, is also evident in both our z- and Y-dropout sample. This relation can be interpreted in terms of a constant surface density of star formation over a range in luminosity of 0.05-1.0L*_z=3.(abridged)