Why is a nick name spelt (Nick)-name?

Nickname
Origin: 1400–50; late ME nekename, for ekename (the phrase an ekename being taken as a nekename). See eke 2 , name; cf. newt (source)

Ekename
Eke“name`\, n. [See Nickname.] An additional or epithet name; a nickname. [Obs.] (source)

Welcome to Fluther, and great question!

I just saw a video explaining it a little bit better (it’s a little NSFW though, bikini). According to that lady an_ekename degenerated into a_nekename. You can find the video here.