Watch out with names, especially foreign ones. The Prussia name is, in German, Preussen (with the beta symbol that my cellphone doesn't have). The pronunciation is significantly different from Prussia in English. Russia on the other hand has, as far as a Google search could provide me, similar pronunciation to the English.

Even so, the word Prussia is theorized to have originated from the slavic Po-Rus ("The Land near Rus") so it's safe to say that yeah, they're related in that sense.

Edit: also, it's important to note that the Prussia region was inhabited by pagan Balts until the 12th century or so. So their cultures weren't entirely unrelated when the name was coined.

Edit 2: as pointed out by several people I mixed Balts with Slavs in my first edit. I've corrected that statement.

They're really only similar in English. Their names in German and Russian respectively is Preußen and Россия [latinized: Rossiya] and not very similar. The Russian name derives from the Rus people, a Varangian tribe. The name Prussia on the other hand comes from the Teutonic conquest of the Prussians tribe/land which is likely named after a river, lake or swamp in the area but to my knowledge there is no certain source of exactly which.

You might also want to check out /r/linguistics.