Which of 不谢 and 不用谢 is correct? When I started to learn Mandarin, I learned on the Rosetta Stone program that it is 不谢 to say "you are welcome" in Mandarin.

However, when I met a Chinese girl in Shanghai, she said that 不谢 is never used and 不用谢 is the only correct word in Mandarin. She is from Nanjing, and we met at Shanghai for your information.

However, now I'm in Chongqing and the host of a room I rented via AirBnB used 不谢 to respond to my 谢谢. I don't know where he is from, for your information.

So now I'm confused. In Mandarin, which is the correct word to say "you are welcome"? Also, is there any difference between regions?
which is the correct word to say "you are welcome"?

Both 不谢 and 不用谢 are correct.

MDBG

不谢


  don't mention it / not at all


不用谢


  You're welcome / Don't mention it


Hell, I have had an old lady tell me: 不用谢谢 - but I wouldn't recommend using this one. 

In the north you might hear 甭(béng)谢, 甭 being a contraction of 不 and 用.

You can also use 不客气


  you're welcome / don't mention it / impolite / rude / blunt