Both words derive from common Slavic root *pali- ("to burn"), but in very different ways.
The Czech word refers to the technology of making the beverage, and has the same etymology as English "brandy" (which ultimately comes from a Germanic root meaning "to burn").
The Russian word comes from the slang word палёный "knockoff, counterfeit" which, as most Russian slang words, has an obscure etymology. In its direct sense, it means "burnt". As a slang word, it is speculated to come from самопальный "homemade, homebrewed", which is thought to be a humorous paronomastic contamination of самодельный "self-made" with самопал "zip gun".
The word самопал, literally "self-firing", is a revived XVI century word. Originally it described a kind of firearm used by the Russian army, which had later fallen out of use. The adjective самопальный in its original meaning outlived the firearm, and came to mean "related to firearms", but also fell out of use by XVIII century.
Whatever the way палёнка came to mean "counterfeit spirit", it ultimately comes from the same root, meaning "to burn", as the Czech word.