Deitmar and Echterhoff "Principles in Harmonic Analysis" Chapter 9 and 11 for the cocompact case (Hejhal I). It requires some familiarity with representation theory, but you seem to be more interested in a conceptual approach. It is the only source which really made me understand the underlying concepts of the trace formula.

In chapter 9, the main result is as follows:

Given a cocompact subgroup $\Gamma$ in a unimodular group $G$, convolution operators $T_\phi$ for functions $\phi \in C_c^\infty(G)$ on $L^2( \Gamma\backslash G)$ are trace class operators. The formula for the trace is given as
$$ tr T_\phi = \sum\limits_{conj.classes in \Gamma} vol(\Gamma_\gamma \backslash G_\gamma) \int\limits_{G_\gamma \backslash G} \phi(g \gamma g^{-1}) \,d\,g.$$
The space $L^2( \Gamma\backslash G)$ decomposes of course into irreducible reps. It is a nice exercise to deduce the Poisson summation formula from this.

In chapter 11, they specialize this to the situation $G=SL(2,\mathbb{R})$ and $\Gamma$ has only hyperbolic elements.

The non-compact situation is more difficult (Hejhal II). The main idea (working with $G$) is mostly hidden in Selberg's and Hejhal's presentation, and the underlying computations with special functions can be avoided until a certain point (Chapter 11 is the analogue). This is where these guys start. Iwaniec "Spectral methods" is pretty close to Selberg's Göttingen lecture notes. Hejhal and Selberg are in my opinion a terrible point to enter the subject for an algebraic person. Hejhal remains the most important reference for researchers. Similar route is done for quadratic imaginary fields in Elstrodt, Grunewald, Mennicke "Hyperbolic Groups acting...".

It will be probably more useful to understand the Arthur trace formula as presented in Jacquet-Gelbart "Analytic aspects...." given your background. Knightly and Li "Trace of Hecke operators" are useful here for the Hecke eigenvalues, and the lecture notes by Gelbart for the general theory.

My thesis might be interesting to you, because I generalize the computations of Hejhal II/Knightly-Li to the number field case and "arbitrary" congruence subgroups by using Arthur's trace formula and the adelic framework: http://webdoc.sub.gwdg.de/diss/2012/palm/. As an example, I derive the Selberg trace formula from the Arthur trace formula there.