I would approach this a little differently.
Suppose you want to test a particular piece of functionality, e.g. logging in.
You first need to navigate to the login page, which may succeed or fail. Failure doesn't mean your test is failing; it means a precondition of your test, namely, being able to navigate to the login page, is failing. That's not what you're testing in this test.
Once you've arrived on the login page, you can attempt to log in, which may succeed or fail. This is the test you want to perform. If your test is correct, the results will correctly indicate whether logging in worked or not.
This is true in general: tests may generally have preconditions that aren't part of the test, but that can be tested themselves.
I think what you're trying to say is that many different paths may cause the precondition (in this case: the login page being reached) to be fulfilled, and testing those paths really should be separated from running the test that that precondition is a precondition for. We want to test those paths separately, and once we think they are reliable, use any of them to fulfill the precondition for the present test.
This can be formulated differently by saying: we'll assume that using the application will put us into certain consecutive states, and what we want to do is test each transition between states. Certain sequences of actions will (if they go well) bring us into a certain state, suitable as a starting point for performing the test we want to perform. The test will then perform another action, that is supposed to bring us into a certain state (the transition), and from the test we will be able to determine whether that state has actually been reached (whether the transition happened that is supposed to happen).
We can express this by modeling the behavior of the application as a state machine that contains the states the application can be in and the state transitions we want to test.
However, we also need to take input and output into account. Sometimes, state transitions depend on user input. For instance, supplying a correct combination of username and password produces the state of being logged in; supplying an incorrect combination produces the state of not being logged in. Furthermore, the output we see (the webpage being produced) may not correspond to a specific state, it may also depend on which transition was taken to arrive into that state. For instance, when a login attempt fails, we will see an error message, but the resulting state is one of not being logged in, not one of being shown an error message.
Therefore, it's a good idea to introduce input and output into the model, which turns our model into an I/O automaton.
So the idea is to specify the application's behavior using an I/O automaton, then to write tests to test each of its transitions. Given those tests, you can automatically generate a complete test suite to test the whole system, using various strategies. I even know a piece of software designed to do this: JTorX.
We'll need to add parametrization. For instance, when logged in, we're logged in as a specific user. The user we're logged in as is a parameter to the state of being logged in. We may need to check whether we're logged in by checking whether certain attributes of that user appear in certain positions on the page. So being able to parametrize the model by user may be important.
Furthermore, I'd factor the state machine into a Petri net or similar. For instance, being logged in is not really a state; it is an attribute of a state. Typically, being logged in we can do everything we can do when not logged in (except logging in), plus a couple of things we need to be logged in for. This can be modeled using Petri nets or some derivative (some sort of colored Petri net).
This approach will provide structure and meaning to your endeavor. Your 100 test scenarios will be paths in your I/O automaton transition graph. Your 10 paths are those of the 100 that lead from the initial state to the state in which you need to be in order to start the test at hand. The whole thing will be incomparably more understandable and concise than just specifying a zillion test scenarios and trying to group them afterwards.
Too bad Selenium, TestNG, or anything else I've worked with don't support this approach directly. If I were still working in test automation, I might have written something that does by now. The JTorX software is dead, as far as I know, but it may still be usable, or alternatives may be out there that use the same approach.