The melting-like transitions of Na-8 and Na-20 are investigated by ab initio constant energy molecular dynamics simulations using a variant of the Car-Parrinello method which employs an explicit electronic kinetic energy functional of the density, thus avoiding the use of one-particle orbitals. Several melting indicators are evaluated in order to determine the nature of the various transitions, and are compared with other simulations. Both Na-8 and Na-20 melt over a wide temperature range. For Na-8, a transition is observed to begin at similar to 110 K, between a rigid phase and a phase involving isomerizations among the different permutational isomers of the ground state structure. The "liquid" phase is completely established at similar to 220 K. For Na-20, two transitions are observed: the first, at similar to 110 K, is associated with isomerization transitions among those permutational isomers of the ground state structure which are obtained by interchanging the positions of the surface-like atoms; the second, at similar to 160 K, involves a structural transition from the ground state isomer to a new set of isomers with the surface molten. The cluster is completely liquid at similar to 220 K.