Why don't you enhance the service to take care of deleting the stored data when:
- The user does not complete the form and navigates away from the entire form submission process
- The user submits the form
Basically, you could enhance your service as follows:
myApp.factory('myService', function () {
    var formData = {};
    return {
        getData: function () {
            //You could also return specific attribute of the form data instead
            //of the entire data
            return formData;
        },
        setData: function (newFormData) {
            //You could also set specific attribute of the form data instead
            formData = newFormData
        },
        resetData: function () {
            //To be called when the data stored needs to be discarded
            formData = {};
        }
    };
});
Your controller could then be as follows:
myApp.controller('FirstStepCtrl', ['$scope', 'myService', function ($scope, myService) {
    //This is the controller of the first step in the form
    //Reset the data to discard the data of the previous form submission
    myService.resetData();
    //Remaining Logic here
}]);
myApp.controller('LastStepCtrl', ['$scope', 'myService', function ($scope, myService) {
    //This is the controller of the last step in the form
    //Submits the form
    $scope.submitForm = function () {
        //Code to submit the form
        //Reset the data before changing the route - assuming successful submission
        myService.resetData();
        //Change the route
    };
    //Remaining Logic here
}]);
Another alternative is to call the service's resetData() function when the route changes to something that is not within the form application. If you have something like a Parent Controller for the Form step controllers, then in that controller, you could keep a watch over the route change:  
$scope.$on('$routeChangeStart', function() { 
   //Use $location.path() to get the current route and check if the route is within the 
   //form application. If it is, then ignore, else call myService.resetData()
   //This way, the data in the forms is still retained as long as the user is still
   //filling up the form. The moment the user moves away from the form submission process,
   //for example, when explicitly navigating away or when submitting the form, 
   //the data is lost and no longer available the next time the form is accessed
 });