This is a very important question which bothered me for a long time by until I saw the explanation of Rav Yeruchom Perlow in his introduction to the commentary on the Sefer HaMitzvos of Rav Sa'adyah Gaon.

The question that he addresses is why some of the Gaonim and Early Rishonim invested so much time and effort in working out the list of the 613 mitzvos. He answered that since on the one hand Chazal teach in several places that there are 613 mitzvos, and on the other hand there are clearly many more mitzvos than this, a set of rules are needed in order to determine which mitzvos should be included in the list of 613. Each one of these early authorities had his own set of rules (the Rambam spells out clearly what his rules are) and thus they each end up with a different list.

And the importance of working out which mitzvos go into the list is this: there are many mitzvos mentioned in the gemara which are not clear if they are d'oraisa (from the Torah) or d'rabanan (from the Rabbis). Even when a mitzvah seems to be derived from a posuk sometimes it is only an asmachta (a mitzvah d'rabanan which is supported by the Torah, but which does not come from the Torah). But if the mitzvah is in the list of the 613, then it is most definitely d'oraisa. And if it is not in the list then the determination of whether a certain mitzvah is d'oraisa or d'rabanan has to be made some other way, or remains a doubt.