Your questions get more and more thoughtful and deep. This is great. On the other hand, for a language learner just memorizing the case is just fine; with practice, the correct case would come to you intuitively. Unless, of course, if you, indeed, are looking for an insightful and research-based answer.
Short answer: both are correct. It depends on where do you like to place the Subject at.
So we are talking about Nominative vs. Genitive.
Observation 1: The Subject always goes in Nominative; the Nominative unequivocally points to the Subject.
Observation 2: There can be subjectless sentences; in this case, all nouns have case other than Nominative.
- Мені(Dat) треба води(Gen) (roughly, "to me needed water") — here we have a subjectless sentence where none of я/мені or вода/води are Subjects.
Somewhat similar to what you see in English sentences like "it is raining" where "it" acts as a dummy subject.
- Confer: "я потребую води" (I need water) where all Subject-Verb-Object are clear.
- Note: води Genitive comes from an ancient Partitive case.
- Мені(Dat) потрібна вода(Nom) (roughly, "water is needed for me") — here вода is the Subject! Note that потрібна(Adjective) is agreed with вода(Feminine).
- Confer: "мені потрібний дім", ("I need a house") the Adjective agrees with дім(Masculine).
Observation 3: Animate nouns (including those having facultative animacy) may shift your preference toward #2. For example, "мені потрібна машина" ("I need a car") subjectively sounds more natural to me (with вода both options sound equally correct).
Summarizing all above,
- If you think that the main logical focus goes to мені (which, I believe, is the most common use), then use "мені треба води";
- If the main focus goes to вода (especially if you want to emphasize the contrast, e.g. when someone gives you beer instead of water ;-), you should use "мені потрібна вода".