Hi Sparkky,
You can run large tilemaps perfectly fine, limited by the size of the mesh in memory right now (2D Toolkit doesn't stream tilemap geometry in or generate data on as the camera moves).
It splits up your tilemap into chunks by default - so if you had a 512x512 tilemap with 32x32 chunks, each chunk will be built out of 32x32 tiles. Each chunk is a separate renderable elemtent, so those not visible will get culled out. tk2d also will not generate data for empty chunks.
Having said that though, 10k x 10k tiles is rather large though. Fully populated, that would be 400,000,000 vertices. It shouldn't be a problem to render (depends entirely on how fast Unity culls objects), but memory cost would be far too prohibitive. If you were going for something that big, I suggest setting up different scenes and streaming them in and out for various parts of the world. Obviously it won't be a problem if you dont fully populate the map.
If you don't care about collider meshes, it should be possible to make it "stream" (generate mesh data on the fly) with a few changes here and there - I'd probably be able to help / point in the right direction there. Generating collider mesh data is far too expensive to do at runtime.
So yeah, the answer to your question isn't that straightforward.
Anyway, hope that helps. Feel free to ask if you have any further questions.