We propose a quad-tree scheme for obtaining sub-pixel estimates of interframe motion in the frequency domain. Our scheme is based on phase correlation and uses motion compensated prediction error to control the partition of a parent block to four children quadrants. This criterion guarantees a monotonic decrease of the motion compensated prediction error with an increasing number of iterations making our scheme suitable for embedded coding applications. Our results show that our scheme provides a better level of adaptation to scene contents and outperforms fixed block size phase correlation in terms of total motion compensated prediction error for the same number of motion vectors and also in terms of number of motion vectors for the same level of motion compensated prediction error.