Allright so basically I am making a map for a worldspace the size of shivering isles.

I am thinking of making a world map for it which will have a size of 4096 x 4096 ...

However I noticed that Oblivion's original map is half that size; 2098 x 2098 or lower. Does this matter? I mean can I add map larger than this size work or not?

The limiting factor is the size of texture (not image) that your graphics card can handle. When the game came out, only cards for gaming computers could handle as high as 2048x2048. I more recent years, 4096x4096 became the maximum texture size (although many users still can't handle that high). Right now I think there are some cards which can handle 8192x8192. It's specifically a hardware thing. The point to remember however is that the larger the image size used for the map, the larger the map becomes (since there are more pixels between Skingrad and IC for instance). Meaning that even if you have hardware that can support extremely large textures, you may end up just having to needlessly scroll around the map to find a location, and will almost certainly see things on the map which don't quite line up.

Distilling Vagrant0's reply a little:

The pixel resolution of the map used is directly what is shown on the screen. There is no scaling of the image. So to provide for users with different screen sizes (and shapes) there are three versions of the standard maps in full-sized, half-sized, and 80% scales, in the Menus, Menus50 and Menus80 folders. You'll need to provide the scaled-down copies of your map.

The entire map has to be in the graphic memory so you can scroll around it. This may affect what video cards can run your mod, depending on how much memory is available.

Taking the two together, however, those users with low-end cards will be running at lower resolutions and using a smaller copy of the map. It may still be an issue for low-res users that the smallest map is now 2048x2048.

If you're not releasing the mod for anyone else to play, it's not a problem!