Same problem here s health was telling me I was running super slow but I felt like I was doing all right. At the end it gave me this summary. Nice math Samsung! This was on a new S6 Active.
My Galaxy Note 4 displays "5 km/h" when I walk. If I begin to run but still at 5 km/h, the speed increases to 8 km/h. My wife's Note 3 has the same problem.