Counting \((p,q)\)-bicliques in bipartite graphs is crucial for a variety of applications, from recommendation systems to cohesive subgraph analysis. Yet, it remains computationally challenging due to the combinatorial explosion to exactly count the \((p,q)\)-bicliques. In many scenarios, e.g., graph kernel methods, however, exact counts are not strictly required. To design a scalable and high-quality approximate solution, we novelly resort to \emph{\((p,q)\)-broom}, a special spanning tree of the $(p,q)$-biclique, which can be counted via graph coloring and efficient dynamic programming. Based on the intermediate results of the dynamic programming, we propose an efficient sampling algorithm to derive the approximate $(p,q)$-biclique count from the \((p,q)\)-broom counts. Theoretically, our method offers unbiased estimates with provable error guarantees. Empirically, our solution outperforms existing approximation techniques in both accuracy (up to 8$\times$ error reduction) and runtime (up to 50$\times$ speedup) on nine real-world bipartite networks, providing a scalable solution for large-scale \((p,q)\)-biclique counting.