I started playing in november, casually. Then in december till january, i play skyrim in hardcoe mode, mostly testing mods and playing the game etc.
I use mods, but lately i did not add any new mods.
Now i find that ever since november, my game starts up slower and slower everyday. Last month(febuary) it takes about 15 sec to start skyrim. Now, it takes like 2min... and it isnt looking good. And no, i didnt add any new mods.

Additionally, during gameplay, going into cities/moving maps seem to load longer and longer than before. In febuary, entering solitude is roughly 10 sec, but now it takes FOREVER.
And it happens to every new char i create too. Even quicksave on a new character, which used to take <1 sec to save, now takes 10 sec, and the screen simply hanged. The save file is roughly 3-4mb
whats going on ?!

Delete your old game saves. My Documents --> My Games --> Skyrim --> Saves

Do as suggested above, also does this happen with any other games or only skyrim? Unless its skyrim specific, sounds like a failing hdd to me.

At least test your saves - rename the folder and let a new one build. Start a new game and see if it helps. You might also want to delete your Skyrim .ini and Prefs files and let new ones build. Sometimes that's all it takes to get things back in order.