Both are animals connected with fire.
The word salamander comes from the Arabic, and means "lives in fire". The myth behind the name is that people would put logs on campfires and be amazed when these little creatures scuttled out. They thought that they could withstand the flames, but that's not true.
The phoenix was a mythological bird who, at the end of its life, would builds itself a nest of twigs that it then ignited; both the nest and the bird burned fiercely and were reduced to ashes, from which a new, young phoenix arose.
In both cases, there is a connection with the idea of fire and life: the salamander lives in fire while the phoenix creates new life from the fire.