Given that I don't know exactly which relation you're talking about, I'll give you something old and something new:
A priori, asking for a formula for the number of fixed points of Atkin-Lehner is asking for the trace of the matrix representing the Atkin-Lehner involution. Hence you're asking for a trace formula. The earliest (and most general) reference I can think of for such a thing is
Eichler, M. Modular correspondences and their representations. J. Indian Math. Soc. (N.S.) {\bf 20} (1956), 163-206.
Now a more modern view of fixed points of the Atkin-Lehner involution $w_m$ is that they're in bijection with conjugacy classes of embeddings $\mathbf{Z}[\sqrt{-m}] \hookrightarrow \mathcal{O}_0(N)$, the order used to define the Shimura curve $X^D_0(N)$. You said you wanted me to sweep the CM theory under the rug, so I won't elaborate on Shimura curves.
Anyways, this can by done by counting conjugacy classes of optimal embeddings of either $R = \mathbf{Z}[\sqrt{-m}]$ or $\mathbf{Z}[\dfrac{1 + \sqrt{-m}}{2}]$ into your quaternion order.
For counting these things, probably the book of Vigneras is best, but I like the exposition of Santiago Molina here http://www.crm.es/Publications/10/Pr928.pdf or here http://arxiv.org/PS_cache/arxiv/pdf/0912/0912.5217v4.pdf (same paper in section 2)
In particular if we simplify things and say that $\mathbf{Z}[\sqrt{-m}]$ is a maximal order, every embedding is optimal, and so the number of fixed points of $w_m$ is
$$h(-4m)\prod_{p|D}\left(1 -\left(\dfrac{-4m}{p}\right)\right)\prod_{q|N}\left(1 +\left(\dfrac{-4m}{q}\right)\right)$$