This is a question that analytic philosophers have been asking since the latter part of the 19th Century. Many would argue this question is the formation foundation of analytic philosophy starting with Alfred Whitehead and Bertrand Russell’s attempt at uniting logic and mathematics —-in their Principia Mathematica advocating the “logicism” view that all mathematical truths are logical truths. Despite the fact that such logic as Godel’s Incompleteness Theorem seems to break the connection between logic and mathematics, logicism continues to be a force in present meta-logic and philosophy of mathematics. Most mathematicians seem to be Platonist or formalist advocating that mathematics has its own distinct foundation in a real but distinct mathematical reality or in the formalism of Zermelo-Fraenkel set theory. Supposedly, Russell finally gave up on logicism and concluded, “[t]o a mind of sufficient intellectual power, the whole of mathematics would appear trivial, as trivial as the statement that a four-footed animal is an animal”. Whitehead eventually saw logic as a tool for aiding “mathematical intuition” to see patterns in reality —- not sure what one would call a view such as this; he eventually, as so many philosophers have done as they got older, got into writing a lot but saying nothing. So, to answer your question, the answer is that there is no definite answer; depends on who you ask. Logic and math seem to have something in common. Beyond language? Maybe nothing.
Personally, I would say the foundation of both logic and mathematics lies in the consciousness and its creation of rule-following as a means to deal teleologically with reality. Because this foundation as does consciousness precedes words and language, it is what Wittgenstein accurately described as something “whereof one cannot speak, thereof one must be silent”. However, no one is silent about it, we all ask and talk about it because —- well, why not? Your question is similar to asking what is the relationship between musical notation and music? There are plenty of great musicians who play by ear and cannot read any musical notation. There are arrangers who are lousy musicians — in fact these days, you can program a computer to listen to music and to write up musical notation for it. You can arrange a song, stick it in a drawer, and no one ever plays it; is that music? Musical notation and music seem to have something in common but they are different. Clearly, one cannot have music without notes nor notes without music, so what do they have in common? (Here is an interesting contemplation that may shed light on your question. The Beatles could not read or write music — at least not in their early career before they got wealthy and older with the money and time to learn. So, the story goes, they “wrote” their songs with the only rule following consisting of one simple rule: that they record only songs they could easily remember; if they could not remember by ear how it was played, they junked it. Later, the songs generated by this one simple rule were transcribed by other people into the reality of written music through the complex language rule-following of musical notation and its complex semantics and syntax. For example, the story goes, when the Beatles producer George Martin was writing down the melody of the famous A Hard Day’s Night, in the line “[a]nd I’ve been working like a dog”, he could not translate the note Lennon was singing, so he asked Lennon if it was an E or F, and Lennon replied “Yeah, one of those.” Martin went with F. Was it really an F, or should have Martin written it as an E? Will we ever know?).