I know they attended Schelling's lectures together but that's it. Did they ever have a written correspondence or even talk to each other?
They're both contemporaries but had completely different ideas. It'd be interesting to know if they historically interacted with each other.
Doubtful. Kierkegaard never mentions Engels in his published writings or his journals and papers, and there doesn’t seem to be anything in the secondary literature about such a correspondence, either (e.g., in Kierkegaard and His German Contemporaries: Philosophy, ed. Stewart).
Kierkegaard did, however, discuss class conflict with King Christian VIII, albeit somewhat superficially and not at great length: “Then we started to converse, for a time walking about as we did so. He always preferred talking about governmental matters or commenting in general on one or another political issue. That day he turned the conversation to communism, about which he obviously was anxious and afraid. I explained that, as I understood it, the whole movement confronting us would be a movement that would not touch the kings at all. It would be a class conflict, but it would always be to the interests of the conflicting parties to get on well with the monarch. The problems were ancient ones returning again, and thus it was easy to see that in a way the king would come to stand outside them. It would be like household disputes between the basement and the first floor, between these two and the second floor, etc., but the landlord would not be attacked” (Søren Kierkegaard’s Journals and Papers 6: 6310).
The most helpful discussion I can find on the matter is Gregor Malantschuk’s Den Kontroversielle Kierkegaard, which briefly discusses Kierkegaard’s scant knowledge of communism, and claims Kierkegaard did not know of Marx and Engels’ brand but knew of communism only through theorists such as Pierre-Joseph Proudhon. Malantschuk contrasts some of Kierkegaard’s and Marx’s views, but leaves Engels out of it. He also says it’s interesting that Works of Love “came out the same autumn in which Marx and Engels undertook the task of drawing up the Communist Manifesto, published in February of the following year” insofar as the former “stands as a program script for a view of life diametrically opposed to what is expressed” in the latter.