We demonstrate a direct correlation between the domain structure of multiferroic BiFeO3 thin films and exchange bias of Co0.9Fe0.1/BiFeO3 heterostructures. Two distinct types of interactions, an enhancement of the coercive field (exchange enhancement) and an enhancement of the coercive field combined with large shifts of the hysteresis loop (exchange bias), have been observed in these heterostructures, which depend directly on the type and crystallography of the nanoscale (2 nm) domain walls in the BiFeO3 film. We show that the magnitude of the exchange bias interaction scales with the length of 109 degree ferroelectric domain walls in the BiFeO3 thin films which have been probed via piezoresponse force microscopy and x-ray magnetic circular dichroism.