We study the problem of tracking low radar cross section (RCS) objects using a range doppler sensor. Previously proposed track-before-detect (TBD) algorithms for this problem do not scale to large scenes, as their computational complexity grows rapidly with increasing grid size. In this paper we present a novel tracking algorithm that controls the complexity of the tracking algorithm using an adaptive multi-resolution grid to represent state of the objects in the scene, with finer cells at regions with higher probability of presence of active targets. We present extensive simulation results to illustrate the superior scaling performance of our technique.