Not exactly a reference, but I found some discussion of this formula in Bill Tutte's graph-theoretic memoirs, *Graph Theory as I Have Known it* (Oxford, 1998). In Chapter 5 ("Algebra in Graph Theory"), he writes:

In their study of complexities or tree-numbers the Four made much use of the recursion formula
$$C(G) = C(G'_A) + C(G''_A)$$
When I was doing my PhD research I began to collect other functions of graphs that satisfied similar recursions. (p.53)

The "Four" that Tutte is referring to here are: R. L. Brooks, C. A. B. Smith, A. H. Stone, and W. T. Tutte. (He mentions that they all met as students at Cambridge in the Trinity Mathematical Society.) So perhaps this deletion-contraction formula was folklore at the time, or at least "Fourlore".

I think that the connection to Kirchhoff's theorem is indirect, corresponding to the fact that the "complexity" and the "tree-number" of a graph coincide. Tutte explains in Chapter 1 ("Squaring the square"):

We learned that Kirchhoff's Laws for a network $N$ were associated with a special matrix $K(N)$ called, by us at least, the Kirchhoff matrix of $N$. [...] We learned that the determinant of the matrix $K_i(N)$ obtained from $K(N)$ by striking out the $i$th row and column was independent of $i$. We decided to call its value the "complexity" $C(N)$ of $N$. (p.7)

[...]

By expanding a determinant it can be shown that the number of spanning trees of $G$ is the complexity $C(G)$ of $G$. For a general electrical network $N$ the complexity $C(N)$ proves to be the sum over all the spanning trees of $N$ of the products of the conductances of their edges. This result is known as the Matrix-Tree Theorem, and it goes back to Kirchhoff. (p.11)