From "New Research in Logic" (1912, when Heidegger was 23), translated in "Becoming Heidegger", p. 33. To the best of my knowledge, this is the only time Frege is mentioned in Heidegger's corpus. I would be interested to learn otherwise, if I'm wrong about this.
Nevertheless, we ourselves are inclined to attribute a far-reaching significance to Husserl's penetratingly profound and very propitiously formulated Investigations, for they have truly broken the psychological spell and brought the above-mentioned clarification of principles into play. Husserl here does not hesitate to express his gratitude for the influential suggestions that he received from the Wissenschaftlehre (1837) of the Austrian mathematician and philosopher Bernard Bolzano. The planned reprint of this now rare book will probably soon appear. In this connection, the name of a German mathematician cannot be left unmentioned. Gottlob Frege's logical-mathematical researches are in my opinion not yet appreciated in their true significance, let alone exhausted. What he has written in his works on "Sense and Meaning" and on "Concept and Object" cannot be disregarded by any philosophy of mathematics. But it is also equally valuable for a universal theory of the concept. While Frege overcame psychologism in principle, Husserl in his Prolegomena to a Pure Logic has systematically and comprehensively confronted the essence, relativistic consequences, and theoretical worthlessness of psychologism.